Submission #1188186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188186		anmattroi	Toy Train (IOI17_train)	C++17	11 / 100	4 ms	1860 KiB

train

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

int selfLoop[maxn];
vector<int> adj[maxn], Stack, g[maxn];

int cl[maxn], num[maxn], low[maxn], lt[maxn], slt = 0, cool[maxn], id = 0, charged[maxn];

void pfs(int u) {
    num[u] = low[u] = ++id;
    cl[u] = 1;
    Stack.emplace_back(u);

    for (int v : adj[u])
    if (!cl[v]) {
        pfs(v);
        low[u] = min(low[u], low[v]);
    } else if (cl[v] == 1) low[u] = min(low[u], num[v]);

    if (num[u] == low[u]) {
        ++slt;
        int hasCharged = 0, sz = 0;
        int v;
        do {
            v = Stack.back(); ++sz;
            hasCharged |= (charged[v]);
            Stack.pop_back();
            cl[v] = 2;
            lt[v] = slt;
        } while (v != u);
        cool[slt] = ((sz > 1 || (selfLoop[v])) && (hasCharged));
    }
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
    int n = a.size(), m = u.size();
    for (int i = 0; i < m; i++) {
        if (u[i] == v[i]) selfLoop[u[i]] = 1;
        else adj[u[i]].emplace_back(v[i]);
    }
    for (int i = 0; i < n; i++) charged[i] = r[i];
    for (int i = 0; i < n; i++) if (!cl[i]) pfs(i);
    for (int i = 0; i < m; i++)
    if (lt[u[i]] != lt[v[i]])
        g[lt[u[i]]].emplace_back(lt[v[i]]);

    for (int i = 1; i <= slt; i++)
        for (int j : g[i]) {
            assert(j < i);
            cool[i] |= cool[j];
        }

    vector<int> ans;
    for (int i = 0; i < n; i++) ans.emplace_back(cool[lt[i]]);
    return ans;
}

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