Submission #1206476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206476		onbert	Toy Train (IOI17_train)	C++20	23 / 100	161 ms	1884 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005, INF = 1e6;
int n, m;
vector<int> own, ans, charge, station;
vector<int> adj[maxn], radj[maxn];
int cnt[maxn];

void dfs(int u) {
    // cout << u << " " << ans[u] << endl;
    for (int v:radj[u]) if (ans[v] == -1) {
        cnt[v]++;
        if (own[v] == 1 && ans[u] == 1) {
            ans[v] = 1;
            dfs(v);
        } else if (own[v] == 0 && ans[u] == 0) {
            ans[v] = 0;
            dfs(v);
        } else if (cnt[v] == adj[v].size()) {
            ans[v] = !own[v];
            dfs(v);
        }
    }
}

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V) {
    n = R.size(), m = U.size();
    own = A, charge = R;
    ans.resize(n);
    for (int i=0;i<m;i++) {
        adj[U[i]].push_back(V[i]);
        radj[V[i]].push_back(U[i]);
    }
    for (int i=0;i<n;i++) if (charge[i]) station.push_back(i);

    while (true) {
        for (int i=0;i<n;i++) ans[i] = -1;
        for (int u:station) {
            ans[u] = 1;
            dfs(u);
        }
        for (int i=0;i<n;i++) if (ans[i] == -1) ans[i] = 0;
        vector<int> del;
        for (int u:station) {
            int thing;
            if (own[u] == 1) {
                thing = 0;
                for (int v:adj[u]) thing = max(ans[v], thing);
            } else if (own[u] == 0) {
                thing = 1;
                for (int v:adj[u]) thing = min(ans[v], thing);
            }
            if (!thing) del.push_back(u);
        }
        if (!del.size()) break;
        for (int i:del) station.erase(find(station.begin(), station.end(), i));
    }
    return ans;
}

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