Submission #717240

#	Time	Username	Problem	Language	Result	Execution time	Memory
717240		Jarif_Rahman	Toy Train (IOI17_train)	C++17	100 / 100	834 ms	1968 KiB

train

#include "train.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, m;
vector<vector<int>> graph, graphr;
vector<bool> active;
vector<int> A;

template<int P>
vector<bool> reachable_from(vector<int> S){
    vector<bool> bl(n, 0);
    vector<int> cnt(n, 0);
    for(int i = 0; i < n; i++) if(active[i]) for(int x: graph[i]) cnt[i]+=active[x];

    function<void(int)> dfs = [&](int nd){
        if(!active[nd]) return;
        if(A[nd] != P){
            cnt[nd]--;
            if(cnt[nd] > 0) return;
        }
        if(bl[nd]) return;
        bl[nd] = 1;
        for(int x: graphr[nd]) dfs(x);
    };
    for(int x: S){
        cnt[x] = 0;
        dfs(x);
    }

    return bl;
}

vector<int> who_wins(vector<int> _A, vector<int> R, vector<int> U, vector<int> V){
    swap(A, _A);
    n = A.size(), m = U.size();
    graph.resize(n), graphr.resize(n);
    active.assign(n, 1);
    for(int i = 0; i < m; i++) graph[U[i]].pb(V[i]), graphr[V[i]].pb(U[i]);

    vector<int> ans(n, 1);

    while(1){
        vector<int> S;
        for(int i = 0; i < n; i++) if(active[i] && R[i]) S.pb(i);
        auto bl = reachable_from<1>(S);
        S.clear();
        for(int i = 0; i < n; i++) if(active[i] && !bl[i]) S.pb(i);
        if(S.empty()) break;
        bl = reachable_from<0>(S);
        for(int i = 0; i < n; i++) if(bl[i]) active[i] = 0, ans[i] = 0;
    }

    return ans;
}

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