244972026-02-12 09:44:52Leventusz09Bizonyításcpp17Időlimit túllépés 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Időlimit túllépés1.085s3004 KiB
subtask20/10
3Elfogadva716ms564 KiB
4Időlimit túllépés1.09s820 KiB
5Időlimit túllépés1.09s1780 KiB
6Időlimit túllépés1.09s1332 KiB
7Időlimit túllépés1.09s1524 KiB
8Időlimit túllépés1.088s820 KiB
9Elfogadva259ms580 KiB
10Időlimit túllépés1.09s820 KiB
11Időlimit túllépés1.088s1524 KiB
12Időlimit túllépés1.077s1588 KiB
subtask315/15
13Elfogadva1ms316 KiB
14Elfogadva82ms500 KiB
15Elfogadva3ms316 KiB
16Elfogadva32ms316 KiB
17Elfogadva1ms508 KiB
18Elfogadva143ms520 KiB
19Elfogadva78ms316 KiB
20Elfogadva1ms316 KiB
21Elfogadva3ms456 KiB
22Elfogadva87ms512 KiB
23Elfogadva127ms316 KiB
24Elfogadva1ms316 KiB
25Elfogadva54ms316 KiB
26Elfogadva87ms316 KiB
27Elfogadva26ms472 KiB
28Elfogadva105ms316 KiB
29Elfogadva20ms508 KiB
30Elfogadva2ms316 KiB
31Elfogadva9ms468 KiB
32Elfogadva2ms508 KiB
33Elfogadva1ms316 KiB
34Elfogadva1ms316 KiB
35Elfogadva1ms316 KiB
36Elfogadva82ms508 KiB
37Elfogadva2ms316 KiB
38Elfogadva17ms472 KiB
subtask40/25
39Elfogadva1ms316 KiB
40Időlimit túllépés1.085s2984 KiB
41Elfogadva716ms564 KiB
42Időlimit túllépés1.09s820 KiB
43Időlimit túllépés1.09s1780 KiB
44Időlimit túllépés1.09s1332 KiB
45Időlimit túllépés1.09s1524 KiB
46Időlimit túllépés1.088s820 KiB
47Elfogadva259ms580 KiB
48Időlimit túllépés1.09s820 KiB
49Időlimit túllépés1.088s1524 KiB
50Időlimit túllépés1.077s1588 KiB
51Elfogadva82ms500 KiB
52Elfogadva3ms316 KiB
53Elfogadva32ms316 KiB
54Elfogadva1ms508 KiB
55Elfogadva143ms520 KiB
56Elfogadva78ms316 KiB
57Elfogadva1ms316 KiB
58Elfogadva3ms456 KiB
59Elfogadva87ms512 KiB
60Elfogadva127ms316 KiB
61Elfogadva1ms316 KiB
62Elfogadva54ms316 KiB
63Elfogadva87ms316 KiB
64Elfogadva26ms472 KiB
65Elfogadva105ms316 KiB
66Elfogadva20ms508 KiB
67Elfogadva2ms316 KiB
68Elfogadva9ms468 KiB
69Elfogadva2ms508 KiB
70Elfogadva1ms316 KiB
71Elfogadva1ms316 KiB
72Elfogadva1ms316 KiB
73Elfogadva82ms508 KiB
74Elfogadva2ms316 KiB
75Elfogadva17ms472 KiB
76Elfogadva444ms2112 KiB
77Időlimit túllépés1.085s1076 KiB
78Időlimit túllépés1.085s2728 KiB
79Időlimit túllépés1.083s1076 KiB
80Időlimit túllépés1.077s2732 KiB
81Időlimit túllépés1.077s1584 KiB
82Időlimit túllépés1.077s1772 KiB
83Időlimit túllépés1.092s1232 KiB
84Időlimit túllépés1.077s2032 KiB
85Időlimit túllépés1.077s2092 KiB
86Időlimit túllépés1.077s2220 KiB
87Időlimit túllépés1.08s2732 KiB
88Időlimit túllépés1.082s1524 KiB
89Időlimit túllépés1.082s1524 KiB
90Elfogadva614ms4800 KiB
91Időlimit túllépés1.082s2100 KiB
92Elfogadva609ms4768 KiB
93Időlimit túllépés1.09s2284 KiB
94Elfogadva609ms4768 KiB
95Időlimit túllépés1.09s3176 KiB
96Időlimit túllépés1.1s2992 KiB
97Időlimit túllépés1.078s2092 KiB
98Időlimit túllépés1.088s3008 KiB
99Időlimit túllépés1.09s2992 KiB
100Időlimit túllépés1.1s4516 KiB
101Időlimit túllépés1.088s4516 KiB
102Időlimit túllépés1.087s4520 KiB
103Időlimit túllépés1.077s4580 KiB
104Időlimit túllépés1.1s4516 KiB