30202023-02-08 12:17:27CWMTestnevelés óracpp11Futási hiba 41/50215ms35768 KiB
// Testneveles Ora.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <unordered_set>
using namespace std;
int main()
{
    int pCount, qCount; //People, Query
    cin >> pCount >> qCount;
    vector<vector<int>> Neighbours(pCount+1); //Points at bigger ppl
    vector<int> PeopleSmallerCount(pCount+1); //return smallest->highest
    int SplitIndex = -1; // switch SplitIndex and SplitIndex+1
    for (size_t i = 0; i < qCount; i++)
    {
        int s, b;
        cin >> s >> b;
        Neighbours[s].push_back(b);
        PeopleSmallerCount[b]++;
    }
    queue<int> nextInLine;
    vector<int> Inverted;
    unordered_set<int> Excluded;
    for (size_t i = 1; i < pCount; i++)
    {
        if (PeopleSmallerCount[i] == 0) nextInLine.push(i);
    }
    while (nextInLine.size() != 0) {
        Inverted.push_back(nextInLine.front());
        if (nextInLine.size() > 1 && SplitIndex == -1) {
            SplitIndex = Inverted.size() - 1;
        }
        for (size_t i = 0; i < Neighbours[nextInLine.front()].size(); i++)
        {
            if (Excluded.count(Neighbours[nextInLine.front()][i]) == 0) {
                PeopleSmallerCount[Neighbours[nextInLine.front()][i]]--;
                if (PeopleSmallerCount[Neighbours[nextInLine.front()][i]] == 0) nextInLine.push(Neighbours[nextInLine.front()][i]);
            }
        }
        Excluded.insert(nextInLine.front());
        nextInLine.pop();
    }
    /*cout << Inverted.size();*/
    for (size_t i = 1; i <= pCount; i++)
    {
        if (Excluded.count(i) == 0 && PeopleSmallerCount[i] == 0) {
            SplitIndex = Inverted.size() - 1;
            Inverted.push_back(i);
        }
    }
    if (SplitIndex == -1 && Inverted.size() == pCount) { // only 1 solution
        cout << "1\n";
        for (size_t i = 0; i < Inverted.size(); i++)
        {
            cout << Inverted[i] << " ";
        }
        return 0;
    }
    if (Inverted.size() != pCount) { // 0 solutions
        return 1;
        cout << "0\n";
        return 0;
    }
    if (Inverted.size() == pCount && SplitIndex!=-1) { // 2 solutions
        cout << "2\n";
        for (size_t i = 0; i < Inverted.size(); i++)
        {
            cout << Inverted[i] << " ";
        }
        cout << "\n";
        int a = Inverted[SplitIndex];
        Inverted[SplitIndex] = Inverted[SplitIndex + 1];
        Inverted[SplitIndex + 1] = a;
        for (size_t i = 0; i < Inverted.size(); i++)
        {
            cout << Inverted[i] << " ";
        }
        return 0;
    }
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file
RészfeladatÖsszpontTesztVerdiktIdőMemória
base41/50
1Elfogadva0/03ms1816 KiB
2Elfogadva0/03ms2004 KiB
3Elfogadva0/0211ms22468 KiB
4Elfogadva2/23ms2428 KiB
5Futási hiba0/33ms2632 KiB
6Elfogadva3/33ms2856 KiB
7Futási hiba0/33ms2828 KiB
8Futási hiba0/13ms3060 KiB
9Elfogadva3/33ms3316 KiB
10Elfogadva3/34ms3740 KiB
11Elfogadva3/34ms3720 KiB
12Futási hiba0/14ms3976 KiB
13Elfogadva2/24ms3888 KiB
14Elfogadva3/34ms4144 KiB
15Elfogadva1/1167ms15664 KiB
16Elfogadva3/3178ms30164 KiB
17Elfogadva5/590ms35768 KiB
18Futási hiba0/1215ms35672 KiB
19Elfogadva2/2167ms16388 KiB
20Elfogadva3/3209ms35208 KiB
21Elfogadva4/4211ms35168 KiB
22Elfogadva4/4206ms35260 KiB