244972026-02-12 09:44:52Leventusz09Bizonyításcpp17Time limit exceeded 15/501.1s4800 KiB
#include <iostream>
#include <vector>
#define DEBUG false
using namespace std;

struct Statement {
    int x;
    int y;
    int t;
};

int RM[500][500];
// -1 => nincs út

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;

    for(int i=0; i<N; i++) for(int j=0; j<N; j++) RM[i][j] = -1;

    vector<Statement> T;
    for(int q=0; q<Q; q++){
        int t, x, y;
        cin >> t >> x >> y;
        x--; y--;
        if(t == 1){
            RM[x][y] = q + 1;
            #if DEBUG
            cout << "D" << RM[x][y] << endl;
            #endif
        }else{
            Statement question;
            question.x = x;
            question.y = y;
            question.t = q+1;
            T.push_back(question);
        }
    }

    ///
    for(int _=0; _<500; _++){
        for(int f=0; f<N; f++){
            for(int t=0; t<N; t++){
                if(f==t || RM[f][t] == -1) continue;
                for(int n=0; n<N; n++){
                    if(t==n || f==n || RM[t][n] == -1) continue;
                    int mp = max(RM[f][t], RM[t][n]);
                    if(RM[f][n] == -1) RM[f][n] = mp;
                    if(RM[f][n] > mp) RM[f][n] = mp;
                }
            }
        }
    }

    #if DEBUG
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cout << RM[i][j] << " ";
        }
        cout << endl;
    }
    #endif


    for(int i=0; i<T.size(); i++){
        int rm = RM[T[i].x][T[i].y];
        if(rm == -1 || rm > T[i].t) cout << "NEM" << endl;
        else cout << "IGEN" << endl;
    }

    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Time limit exceeded1.085s3004 KiB
subtask20/10
3Accepted716ms564 KiB
4Time limit exceeded1.09s820 KiB
5Time limit exceeded1.09s1780 KiB
6Time limit exceeded1.09s1332 KiB
7Time limit exceeded1.09s1524 KiB
8Time limit exceeded1.088s820 KiB
9Accepted259ms580 KiB
10Time limit exceeded1.09s820 KiB
11Time limit exceeded1.088s1524 KiB
12Time limit exceeded1.077s1588 KiB
subtask315/15
13Accepted1ms316 KiB
14Accepted82ms500 KiB
15Accepted3ms316 KiB
16Accepted32ms316 KiB
17Accepted1ms508 KiB
18Accepted143ms520 KiB
19Accepted78ms316 KiB
20Accepted1ms316 KiB
21Accepted3ms456 KiB
22Accepted87ms512 KiB
23Accepted127ms316 KiB
24Accepted1ms316 KiB
25Accepted54ms316 KiB
26Accepted87ms316 KiB
27Accepted26ms472 KiB
28Accepted105ms316 KiB
29Accepted20ms508 KiB
30Accepted2ms316 KiB
31Accepted9ms468 KiB
32Accepted2ms508 KiB
33Accepted1ms316 KiB
34Accepted1ms316 KiB
35Accepted1ms316 KiB
36Accepted82ms508 KiB
37Accepted2ms316 KiB
38Accepted17ms472 KiB
subtask40/25
39Accepted1ms316 KiB
40Time limit exceeded1.085s2984 KiB
41Accepted716ms564 KiB
42Time limit exceeded1.09s820 KiB
43Time limit exceeded1.09s1780 KiB
44Time limit exceeded1.09s1332 KiB
45Time limit exceeded1.09s1524 KiB
46Time limit exceeded1.088s820 KiB
47Accepted259ms580 KiB
48Time limit exceeded1.09s820 KiB
49Time limit exceeded1.088s1524 KiB
50Time limit exceeded1.077s1588 KiB
51Accepted82ms500 KiB
52Accepted3ms316 KiB
53Accepted32ms316 KiB
54Accepted1ms508 KiB
55Accepted143ms520 KiB
56Accepted78ms316 KiB
57Accepted1ms316 KiB
58Accepted3ms456 KiB
59Accepted87ms512 KiB
60Accepted127ms316 KiB
61Accepted1ms316 KiB
62Accepted54ms316 KiB
63Accepted87ms316 KiB
64Accepted26ms472 KiB
65Accepted105ms316 KiB
66Accepted20ms508 KiB
67Accepted2ms316 KiB
68Accepted9ms468 KiB
69Accepted2ms508 KiB
70Accepted1ms316 KiB
71Accepted1ms316 KiB
72Accepted1ms316 KiB
73Accepted82ms508 KiB
74Accepted2ms316 KiB
75Accepted17ms472 KiB
76Accepted444ms2112 KiB
77Time limit exceeded1.085s1076 KiB
78Time limit exceeded1.085s2728 KiB
79Time limit exceeded1.083s1076 KiB
80Time limit exceeded1.077s2732 KiB
81Time limit exceeded1.077s1584 KiB
82Time limit exceeded1.077s1772 KiB
83Time limit exceeded1.092s1232 KiB
84Time limit exceeded1.077s2032 KiB
85Time limit exceeded1.077s2092 KiB
86Time limit exceeded1.077s2220 KiB
87Time limit exceeded1.08s2732 KiB
88Time limit exceeded1.082s1524 KiB
89Time limit exceeded1.082s1524 KiB
90Accepted614ms4800 KiB
91Time limit exceeded1.082s2100 KiB
92Accepted609ms4768 KiB
93Time limit exceeded1.09s2284 KiB
94Accepted609ms4768 KiB
95Time limit exceeded1.09s3176 KiB
96Time limit exceeded1.1s2992 KiB
97Time limit exceeded1.078s2092 KiB
98Time limit exceeded1.088s3008 KiB
99Time limit exceeded1.09s2992 KiB
100Time limit exceeded1.1s4516 KiB
101Time limit exceeded1.088s4516 KiB
102Time limit exceeded1.087s4520 KiB
103Time limit exceeded1.077s4580 KiB
104Time limit exceeded1.1s4516 KiB