251162026-02-18 00:53:49999Bizonyításcpp17Time limit exceeded 25/501.08s4408 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;
vector<int> vis;

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

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q;cin>>n>>q;
    v.resize(n);
    b.resize(n,vector<int>(n));
    vis.resize(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{
            for(int &i : vis)i=0;
            int x,y;cin>>x>>y;
            x--;y--;
            cout<<(dfs(x,y)?"IGEN":"NEM")<<'\n';
            /*for(vector<int> i : b){
                for(int j : i){
                    cerr<<j<<' ';
                }cerr<<endl;
            }cerr<<endl<<endl<<"///////////////////"<<endl<<endl;*/
        }
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms500 KiB
2Accepted103ms4408 KiB
subtask210/10
3Accepted1ms500 KiB
4Accepted4ms820 KiB
5Accepted17ms2612 KiB
6Accepted14ms1844 KiB
7Accepted16ms1848 KiB
8Accepted2ms820 KiB
9Accepted1ms316 KiB
10Accepted6ms820 KiB
11Accepted14ms1588 KiB
12Accepted14ms2360 KiB
subtask315/15
13Accepted1ms508 KiB
14Accepted2ms316 KiB
15Accepted1ms500 KiB
16Accepted2ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms500 KiB
19Accepted1ms332 KiB
20Accepted1ms508 KiB
21Accepted1ms316 KiB
22Accepted1ms560 KiB
23Accepted1ms316 KiB
24Accepted1ms508 KiB
25Accepted1ms316 KiB
26Accepted1ms316 KiB
27Accepted1ms396 KiB
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB
31Accepted1ms316 KiB
32Accepted1ms528 KiB
33Accepted1ms316 KiB
34Accepted1ms316 KiB
35Accepted1ms544 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted1ms316 KiB
subtask40/25
39Accepted1ms508 KiB
40Accepted104ms4348 KiB
41Accepted1ms500 KiB
42Accepted4ms820 KiB
43Accepted17ms2612 KiB
44Accepted14ms1844 KiB
45Accepted16ms1848 KiB
46Accepted2ms820 KiB
47Accepted1ms316 KiB
48Accepted6ms820 KiB
49Accepted14ms1588 KiB
50Accepted14ms2360 KiB
51Accepted2ms316 KiB
52Accepted1ms500 KiB
53Accepted2ms316 KiB
54Accepted1ms316 KiB
55Accepted1ms500 KiB
56Accepted1ms332 KiB
57Accepted1ms508 KiB
58Accepted1ms316 KiB
59Accepted1ms560 KiB
60Accepted1ms316 KiB
61Accepted1ms508 KiB
62Accepted1ms316 KiB
63Accepted1ms316 KiB
64Accepted1ms396 KiB
65Accepted1ms316 KiB
66Accepted1ms316 KiB
67Accepted1ms316 KiB
68Accepted1ms316 KiB
69Accepted1ms528 KiB
70Accepted1ms316 KiB
71Accepted1ms316 KiB
72Accepted1ms544 KiB
73Accepted1ms316 KiB
74Accepted1ms316 KiB
75Accepted1ms316 KiB
76Accepted25ms728 KiB
77Accepted17ms1516 KiB
78Accepted83ms3136 KiB
79Accepted17ms1332 KiB
80Accepted59ms2612 KiB
81Accepted23ms924 KiB
82Accepted26ms1076 KiB
83Accepted24ms1588 KiB
84Accepted39ms2192 KiB
85Accepted63ms2964 KiB
86Accepted43ms1176 KiB
87Accepted61ms2628 KiB
88Accepted25ms1524 KiB
89Accepted28ms1844 KiB
90Accepted72ms2864 KiB
91Accepted85ms4148 KiB
92Accepted71ms2860 KiB
93Accepted75ms3380 KiB
94Accepted72ms2868 KiB
95Accepted43ms3124 KiB
96Accepted52ms3892 KiB
97Accepted48ms3892 KiB
98Accepted48ms3124 KiB
99Accepted59ms3380 KiB
100Accepted901ms3380 KiB
101Accepted912ms3324 KiB
102Time limit exceeded1.078s3784 KiB
103Time limit exceeded1.08s3636 KiB
104Accepted866ms3380 KiB