5269 2023. 04. 25 06:17:37 anon Dinók cpp17 Időlimit túllépés 60/100 544ms 92356 KiB 
#include <vector>
#include <queue>
#include <unordered_set>
#include <iostream>

using ll = long long;
using namespace std;

int main()
{
    ll i, j, c, e, t, a, b, N, M;

    cin >> N >> M;

    vector<vector<ll>> ss(M);

    for(i = 0; i < M; i++)
    {
        cin >> t >> a >> b;
        ss[i] = vector<ll> { t, a, b };
    }

    vector<unordered_set<ll>> g(2 * N + 1);

    for(i = 0; i < M; i++)
    {
        switch(ss[i][0])
        {
            case 1:
                g[ss[i][1]].insert(ss[i][2] + N);
                g[ss[i][2]].insert(ss[i][1] + N);
            break;
            case 2:
                g[ss[i][1] + N].insert(ss[i][2]);
            break;
            default:
            break;
        }
    }

    for(i = 1; i <= N; i++)
        g[i].insert(i + N);

    vector<ll> ine(2 * N + 1, 0);

    for(i = 1; i <= 2 * N; i++)
    {
        for(auto x : g[i])
            ine[x]++;
    }

    c = 1;
    vector<ll> ans(2 * N + 1, 0);

    queue<ll> q;

    for(i = 1; i <= N; i++)
    {
        if(!ine[i])
            q.push(i);
    }

    while(q.size())
    {
        e = q.front();
        q.pop();

        ans[e] = c++;

        for(auto x : g[e])
        {
            if(!--ine[x])
                q.push(x);
        }
    }

    for(i = 1; i <= 2 * N; i++)
    {
        if(!ans[i])
        {
            cout << "NEM" << endl;
            return 0;
        }
    }

    cout << "IGEN" << endl;

    for(i = 1; i <= N; i++)
        cout << ans[i] << ' ' << ans[i + N] << endl;

    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1684 KiB
2 Elfogadva 3ms 1928 KiB
3 Elfogadva 10ms 6248 KiB
subtask2 0/5
4 Időlimit túllépés 544ms 83552 KiB
5 Elfogadva 300ms 72232 KiB
6 Elfogadva 237ms 66424 KiB
subtask3 15/15
7 Elfogadva 3ms 2908 KiB
8 Elfogadva 3ms 2972 KiB
9 Elfogadva 3ms 3216 KiB
10 Elfogadva 2ms 3328 KiB
11 Elfogadva 3ms 3328 KiB
12 Elfogadva 3ms 3448 KiB
subtask4 10/10
13 Elfogadva 3ms 3720 KiB
14 Elfogadva 3ms 3492 KiB
15 Elfogadva 3ms 3496 KiB
16 Elfogadva 3ms 3572 KiB
17 Elfogadva 3ms 3656 KiB
subtask5 35/35
18 Elfogadva 3ms 3648 KiB
19 Elfogadva 4ms 4444 KiB
20 Elfogadva 388ms 92144 KiB
21 Elfogadva 485ms 92356 KiB
22 Elfogadva 3ms 4292 KiB
23 Elfogadva 4ms 5216 KiB
24 Elfogadva 229ms 92148 KiB
subtask6 0/35
25 Elfogadva 460ms 88116 KiB
26 Időlimit túllépés 544ms 88120 KiB
27 Elfogadva 402ms 88364 KiB
28 Elfogadva 490ms 88328 KiB
29 Elfogadva 286ms 90524 KiB
30 Elfogadva 433ms 89560 KiB
31 Elfogadva 483ms 88704 KiB
32 Elfogadva 233ms 90780 KiB
33 Elfogadva 215ms 92172 KiB
34 Elfogadva 370ms 89700 KiB
35 Elfogadva 239ms 87056 KiB