251142026-02-18 00:48:31999Bizonyításcpp17Runtime error 0/501.1s262144 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")


vector<vector<int>> v;
vector<vector<int>> b;

bool dfs(int x, int y){
    if(b[x][y])return 1;
    bool temp=false;
    for(int i : v[y]){
        temp|=dfs(x, i);
    }
    b[x][y]=temp;
    return temp;
}

signed main() {
    int n,q;cin>>n>>q;
    v.resize(n);
    b.resize(n,vector<int>(n));
    for(int i = 0;i<n;i++)b[i][i]=1;
    while(q--){
        int t;cin>>t;
        if(t==1){
            int x,y;
            cin>>x>>y;
            v[--y].push_back(--x);
            b[x][y]=1;
        }
        else{
            int x,y;cin>>x>>y;
            x--;y--;
            cout<<(dfs(x,y)?"IGEN":"NEM")<<endl;
            /*for(vector<int> i : b){
                for(int j : i){
                    cerr<<j<<' ';
                }cerr<<endl;
            }cerr<<endl<<endl<<"///////////////////"<<endl<<endl;*/
        }
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Runtime error423ms262144 KiB
subtask20/10
3Runtime error433ms262144 KiB
4Runtime error266ms262144 KiB
5Runtime error360ms262144 KiB
6Runtime error333ms262144 KiB
7Runtime error349ms262144 KiB
8Runtime error282ms262144 KiB
9Runtime error301ms262144 KiB
10Runtime error284ms262144 KiB
11Runtime error344ms262144 KiB
12Runtime error305ms262144 KiB
subtask30/15
13Accepted1ms508 KiB
14Runtime error356ms262144 KiB
15Runtime error264ms262144 KiB
16Runtime error259ms262144 KiB
17Accepted1ms316 KiB
18Runtime error319ms262144 KiB
19Runtime error273ms262144 KiB
20Accepted1ms316 KiB
21Runtime error266ms262144 KiB
22Runtime error287ms262144 KiB
23Runtime error405ms262144 KiB
24Accepted1ms508 KiB
25Runtime error287ms262144 KiB
26Runtime error312ms262144 KiB
27Runtime error289ms262144 KiB
28Runtime error317ms262144 KiB
29Time limit exceeded1.085s176756 KiB
30Accepted1ms316 KiB
31Runtime error273ms262144 KiB
32Runtime error314ms262144 KiB
33Runtime error310ms262144 KiB
34Runtime error261ms262144 KiB
35Accepted1ms508 KiB
36Runtime error305ms262144 KiB
37Runtime error307ms262144 KiB
38Runtime error261ms262144 KiB
subtask40/25
39Accepted1ms508 KiB
40Runtime error465ms262144 KiB
41Runtime error433ms262144 KiB
42Runtime error266ms262144 KiB
43Runtime error360ms262144 KiB
44Runtime error333ms262144 KiB
45Runtime error349ms262144 KiB
46Runtime error282ms262144 KiB
47Runtime error301ms262144 KiB
48Runtime error284ms262144 KiB
49Runtime error344ms262144 KiB
50Runtime error305ms262144 KiB
51Runtime error356ms262144 KiB
52Runtime error264ms262144 KiB
53Runtime error259ms262144 KiB
54Accepted1ms316 KiB
55Runtime error319ms262144 KiB
56Runtime error273ms262144 KiB
57Accepted1ms316 KiB
58Runtime error266ms262144 KiB
59Runtime error287ms262144 KiB
60Runtime error405ms262144 KiB
61Accepted1ms508 KiB
62Runtime error287ms262144 KiB
63Runtime error312ms262144 KiB
64Runtime error289ms262144 KiB
65Runtime error317ms262144 KiB
66Time limit exceeded1.085s176756 KiB
67Accepted1ms316 KiB
68Runtime error273ms262144 KiB
69Runtime error314ms262144 KiB
70Runtime error310ms262144 KiB
71Runtime error261ms262144 KiB
72Accepted1ms508 KiB
73Runtime error305ms262144 KiB
74Runtime error307ms262144 KiB
75Runtime error261ms262144 KiB
76Runtime error310ms262144 KiB
77Runtime error367ms262144 KiB
78Runtime error270ms262144 KiB
79Runtime error326ms262144 KiB
80Runtime error268ms262144 KiB
81Runtime error363ms262144 KiB
82Runtime error405ms262144 KiB
83Runtime error593ms262144 KiB
84Runtime error301ms262144 KiB
85Runtime error441ms262144 KiB
86Runtime error266ms262144 KiB
87Runtime error303ms262144 KiB
88Runtime error264ms262144 KiB
89Runtime error310ms262144 KiB
90Accepted435ms2868 KiB
91Runtime error407ms262144 KiB
92Accepted435ms2940 KiB
93Runtime error389ms262144 KiB
94Accepted474ms3168 KiB
95Accepted225ms3120 KiB
96Accepted233ms4004 KiB
97Accepted177ms4160 KiB
98Accepted277ms3124 KiB
99Accepted312ms3452 KiB
100Time limit exceeded1.082s2324 KiB
101Time limit exceeded1.1s2536 KiB
102Time limit exceeded1.088s2808 KiB
103Time limit exceeded1.09s2732 KiB
104Time limit exceeded1.085s2620 KiB