Submission #25,115

2026-02-18 00:49:59

cpp17

Time limit exceeded 25/50

1.093s

4404 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() {
    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")<<endl;
            /*for(vector<int> i : b){
                for(int j : i){
                    cerr<<j<<' ';
                }cerr<<endl;
            }cerr<<endl<<endl<<"///////////////////"<<endl<<endl;*/
        }
    }
}

Subtask		Sum	Test	Verdict	Time	Memory
	subtask1	0/0
			1	Accepted	1ms	316 KiB
			2	Accepted	340ms	4404 KiB
	subtask2	10/10
			3	Accepted	4ms	508 KiB
			4	Accepted	14ms	564 KiB
			5	Accepted	65ms	2608 KiB
			6	Accepted	46ms	1948 KiB
			7	Accepted	64ms	1808 KiB
			8	Accepted	2ms	820 KiB
			9	Accepted	2ms	316 KiB
			10	Accepted	19ms	760 KiB
			11	Accepted	54ms	1404 KiB
			12	Accepted	50ms	2356 KiB
	subtask3	15/15
			13	Accepted	1ms	508 KiB
			14	Accepted	3ms	316 KiB
			15	Accepted	2ms	316 KiB
			16	Accepted	2ms	316 KiB
			17	Accepted	1ms	388 KiB
			18	Accepted	1ms	428 KiB
			19	Accepted	1ms	316 KiB
			20	Accepted	1ms	316 KiB
			21	Accepted	1ms	316 KiB
			22	Accepted	2ms	316 KiB
			23	Accepted	2ms	316 KiB
			24	Accepted	1ms	380 KiB
			25	Accepted	2ms	392 KiB
			26	Accepted	2ms	416 KiB
			27	Accepted	1ms	316 KiB
			28	Accepted	1ms	508 KiB
			29	Accepted	2ms	316 KiB
			30	Accepted	1ms	316 KiB
			31	Accepted	1ms	316 KiB
			32	Accepted	1ms	500 KiB
			33	Accepted	1ms	580 KiB
			34	Accepted	1ms	316 KiB
			35	Accepted	1ms	316 KiB
			36	Accepted	2ms	316 KiB
			37	Accepted	1ms	316 KiB
			38	Accepted	1ms	316 KiB
	subtask4	0/25
			39	Accepted	1ms	508 KiB
			40	Accepted	365ms	4332 KiB
			41	Accepted	4ms	508 KiB
			42	Accepted	14ms	564 KiB
			43	Accepted	65ms	2608 KiB
			44	Accepted	46ms	1948 KiB
			45	Accepted	64ms	1808 KiB
			46	Accepted	2ms	820 KiB
			47	Accepted	2ms	316 KiB
			48	Accepted	19ms	760 KiB
			49	Accepted	54ms	1404 KiB
			50	Accepted	50ms	2356 KiB
			51	Accepted	3ms	316 KiB
			52	Accepted	2ms	316 KiB
			53	Accepted	2ms	316 KiB
			54	Accepted	1ms	388 KiB
			55	Accepted	1ms	428 KiB
			56	Accepted	1ms	316 KiB
			57	Accepted	1ms	316 KiB
			58	Accepted	1ms	316 KiB
			59	Accepted	2ms	316 KiB
			60	Accepted	2ms	316 KiB
			61	Accepted	1ms	380 KiB
			62	Accepted	2ms	392 KiB
			63	Accepted	2ms	416 KiB
			64	Accepted	1ms	316 KiB
			65	Accepted	1ms	508 KiB
			66	Accepted	2ms	316 KiB
			67	Accepted	1ms	316 KiB
			68	Accepted	1ms	316 KiB
			69	Accepted	1ms	500 KiB
			70	Accepted	1ms	580 KiB
			71	Accepted	1ms	316 KiB
			72	Accepted	1ms	316 KiB
			73	Accepted	2ms	316 KiB
			74	Accepted	1ms	316 KiB
			75	Accepted	1ms	316 KiB
			76	Accepted	172ms	820 KiB
			77	Accepted	32ms	1468 KiB
			78	Accepted	345ms	3168 KiB
			79	Accepted	32ms	1524 KiB
			80	Accepted	222ms	2612 KiB
			81	Accepted	138ms	820 KiB
			82	Accepted	136ms	1076 KiB
			83	Accepted	68ms	1556 KiB
			84	Accepted	120ms	2148 KiB
			85	Accepted	208ms	2968 KiB
			86	Accepted	256ms	1328 KiB
			87	Accepted	221ms	2616 KiB
			88	Accepted	70ms	1456 KiB
			89	Accepted	75ms	1652 KiB
			90	Accepted	493ms	2984 KiB
			91	Accepted	237ms	4140 KiB
			92	Accepted	479ms	2740 KiB
			93	Accepted	226ms	3392 KiB
			94	Accepted	500ms	2872 KiB
			95	Accepted	228ms	3140 KiB
			96	Accepted	241ms	3892 KiB
			97	Accepted	187ms	4076 KiB
			98	Accepted	287ms	3124 KiB
			99	Accepted	321ms	3436 KiB
			100	Time limit exceeded	1.082s	3124 KiB
			101	Time limit exceeded	1.09s	3124 KiB
102	Time limit exceeded		1.085s	3380 KiB
103	Time limit exceeded		1.093s	3368 KiB
104	Time limit exceeded		1.092s	3172 KiB