30152023-02-08 11:36:11CWMTestnevelés óracpp11Wrong answer 38/50211ms35648 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();*/
    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
        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
SubtaskSumTestVerdictTimeMemory
base38/50
1Accepted0/03ms1816 KiB
2Accepted0/03ms2048 KiB
3Accepted0/0211ms22512 KiB
4Accepted2/23ms2508 KiB
5Wrong answer0/33ms2720 KiB
6Accepted3/33ms2932 KiB
7Wrong answer0/33ms3144 KiB
8Accepted1/13ms3360 KiB
9Accepted3/33ms3440 KiB
10Accepted3/34ms3788 KiB
11Accepted3/34ms3688 KiB
12Accepted1/14ms3948 KiB
13Accepted2/24ms3904 KiB
14Accepted3/34ms3900 KiB
15Accepted1/1168ms15400 KiB
16Accepted3/3166ms29964 KiB
17Wrong answer0/535ms35648 KiB
18Wrong answer0/1208ms35580 KiB
19Accepted2/2166ms16176 KiB
20Accepted3/3206ms34932 KiB
21Accepted4/4206ms35220 KiB
22Accepted4/4204ms35136 KiB