Submission #713592

#	Time	Username	Problem	Language	Result	Execution time	Memory
713592		MohamedFaresNebili	Toy Train (IOI17_train)	C++14	100 / 100	1766 ms	1632 KiB

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] = 1;
                    else G[l] = adj[l].size();
                }

                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] && all) || (!A[l] && one))
                        res[l] = 0, R[l] = 0;
                }
            }
            return res;
        }

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51