Submission #1289615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289615		sirnick	Toy Train (IOI17_train)	C++20	100 / 100	225 ms	1552 KiB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;

vector<int> who_wins(vector<int> Own, vector<int> Charge, vector<int> U, vector<int> V) {
    int N = Own.size();
    vector<vector<int>> AR(N), AR2(N);
    int M = U.size();
    for (int i=0; i<M; i++) {
        AR[U[i]].push_back(V[i]);
        AR2[V[i]].push_back(U[i]);
    }

    vector<int> occ(N);
    while (true) {
        vector<int> left(N);
        occ.assign(N, 0);
        for (int i=0; i<N; i++) left[i] = AR[i].size();

        queue<int> Q;
        for (int i=0; i<N; i++) {
            if (Charge[i]==0) continue;
            Q.push(i);
            occ[i] = 1;
        }

        while (!Q.empty()) {
            int x = Q.front(); Q.pop();
            for (int i=0; i<AR2[x].size(); i++) {
                if (occ[AR2[x][i]]) continue;
                left[AR2[x][i]]--;
                if (Own[AR2[x][i]]==1 || left[AR2[x][i]]==0) {
                    occ[AR2[x][i]] = 1;
                    Q.push(AR2[x][i]);
                }
            }
        }

        int rem = 0;
        for (int i=0; i<N; i++) {
            if (Charge[i]==0) continue;
            int cnt = 0;
            for (int j=0; j<AR[i].size(); j++) cnt += occ[AR[i][j]];
            if (cnt==0 || (cnt < (int)AR[i].size() && Own[i]==0)) {
                rem = 1;
                Charge[i] = 0;
            }
        }

        if (rem==0) break;
    }

    return occ;
}

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