Submission #713591

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
713591	2023-03-22T15:03:07 Z	MohamedFaresNebili	Toy Train (IOI17_train)	C++14	0 / 100	1622 ms	1420 KB

train

#include <bits/stdc++.h>

        using namespace std;

        int N, M;
        vector<int> adj[5001], rev[5001];

        vector<int> who_wins(vector<int> A, vector<int> R,
                             vector<int> U, vector<int> V) {
            N = A.size(), M = U.size();
            for(int l = 0; l < M; l++) {
                int X = U[l], Y = V[l];
                adj[X].push_back(Y);
                rev[Y].push_back(X);
            }
            int _N = N;
            vector<int> res(N), G(N);
            while(_N--) {
                queue<int> Q;
                for(int l = 0; l < N; l++) res[l] = 0;
                for(int l = 0; l < N; l++) {
                    if(R[l] == 1) res[l] = 1, Q.push(l);
                    if(R[l]) continue;
                    if(A[l]) G[l] = adj[l].size();
                    else G[l] = 1;
                }

                while(!Q.empty()) {
                    int X = Q.front();
                    Q.pop(); res[X] = 1;
                    for(auto u : rev[X]) {
                        if(--G[u] == 0) Q.push(u);
                    }
                }

                for(int l = 0; l < N; l++) {
                    if(res[l] == 0) continue;
                    bool all = 1, one = 0;
                    for(auto u : adj[l]) {
                        all &= (1 - res[u]);
                        one |= (1 - res[u]);
                    }
                    if((A[l] && one) || (!A[l] && all))
                        res[l] = 0, R[l] = 0;
                }
            }
            return res;
        }

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	616 ms	980 KB	3rd lines differ - on the 14th token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	468 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	199 ms	1420 KB	Output is correct
2	Correct	204 ms	1416 KB	Output is correct
3	Correct	211 ms	1400 KB	Output is correct
4	Incorrect	203 ms	1376 KB	3rd lines differ - on the 1st token, expected: '1', found: '0'
5	Halted	0 ms	0 KB	-