Submission #1188190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188190		anmattroi	Toy Train (IOI17_train)	C++17	0 / 100	647 ms	99636 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 reachable[maxn][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 sz = 0;
        int v;
        do {
            v = Stack.back(); ++sz;
            Stack.pop_back();
            cl[v] = 2;
            lt[v] = slt;
        } while (v != u);
        cool[slt] = (sz > 1 || (selfLoop[v]));
    }
}


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 < n; i++) charged[i] = r[i];
    for (int i = 0; i < m; i++) {
        g[u[i]].emplace_back(v[i]);
        if (u[i] == v[i]) {
            selfLoop[u[i]] = 1;
            continue;
        }
        if (!charged[u[i]] && !charged[v[i]]) adj[u[i]].emplace_back(v[i]);

    }
    for (int i = 0; i < n; i++) if (!cl[i] && !charged[i]) pfs(i);

    for (int i = 0; i < n; i++) {
        fill(cl, cl + n, 0);
        cl[i] = 1;
        queue<int> q;
        q.push(i);
        while (!q.empty()) {
            int u = q.front(); reachable[i][u] = 1; q.pop();
            for (int v : g[u])
            if (!cl[v]) {
                cl[v] = 1;
                q.push(v);
            }
        }
    }


    vector<int> ans(n, 0);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
    if (reachable[i][j] && cool[lt[j]]) {ans[i] = 1; break;}

    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