Submission #1206468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206468		onbert	Toy Train (IOI17_train)	C++20	0 / 100	9 ms	1608 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;
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]) {
            ans[v] = 1;
            dfs(v);
        } else if (own[v] == 0 && !ans[u]) {
            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<n;i++) {
        if (charge[i]) ans[i] = 1;
        else ans[i] = -1;
    }
    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]) {
        int u = i;
        ans[u] = 1;
        dfs(u);
        int thing;
        if (own[u] == 1) {
            thing = 0;
            for (int v:adj[u]) thing = max(ans[v], thing);
        } else {
            thing = 1;
            for (int v:adj[u]) thing = min(ans[v], thing);
        }
        if (!thing) for (int j=0;j<n;j++) ans[j] = 0;
        break;
    }
    for (int i=0;i<n;i++) if (ans[i] == -1) ans[i] = 0;
    return ans;
}

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