Submission #1217506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217506		badge881	Toy Train (IOI17_train)	C++20	100 / 100	411 ms	1740 KiB

train

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

const int mxN = 5005;
const int mxM = 2200005;
const int mxK = 61;
const int MOD = 1e9 + 7;

int N, M;
vector<int> adj[mxN];
vector<int> radj[mxN];
int AB[mxN];
bool imp[mxN];
int cnt;

void init(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
    N = a.size(), M = u.size();
    for (int i = 0; i < N; i++)
        AB[i] = a[i];
    for (int i = 0; i < N; i++)
        imp[i] = r[i];
    for (int i = 0; i < M; i++)
    {
        int t1 = u[i], t2 = v[i];
        adj[t1].push_back(t2);
        radj[t2].push_back(t1);
    }
}
bool Chk[mxN];
bool bor[mxN];
int deg[mxN];
queue<int> que;
void solve_reachable()
{
    for (int i = 0; i < N; i++)
        deg[i] = adj[i].size(), Chk[i] = false;
    for (int i = 0; i < N; i++)
        if (imp[i])
            que.push(i), Chk[i] = true;
    while (que.size())
    {
        int now = que.front();
        que.pop();
        for (int x : radj[now])
            if (!Chk[x])
            {
                if (AB[x] == 1)
                {
                    Chk[x] = true;
                    que.push(x);
                }
                else
                {
                    deg[x]--;
                    if (deg[x] == 0)
                    {
                        Chk[x] = true;
                        que.push(x);
                    }
                }
            }
    }
    for (int i = 0; i < N; i++)
        bor[i] = (!Chk[i]);
}
void destroy_charge()
{
    for (int i = 0; i < N; i++)
        deg[i] = adj[i].size(), Chk[i] = false;
    for (int i = 0; i < N; i++)
        if (bor[i])
            que.push(i), Chk[i] = true;
    while (que.size())
    {
        int now = que.front();
        que.pop();
        for (int x : radj[now])
            if (!Chk[x])
            {
                if (AB[x] == 0)
                {
                    Chk[x] = true;
                    que.push(x);
                }
                else
                {
                    deg[x]--;
                    if (deg[x] == 0)
                    {
                        Chk[x] = true;
                        que.push(x);
                    }
                }
            }
    }
    for (int i = 0; i < N; i++)
        if (Chk[i])
            imp[i] = false;
}
void solve()
{
    int pcnt = 0;
    for (int i = 0; i < N; i++)
        if (imp[i])
            pcnt++;
    while (true)
    {
        solve_reachable();
        destroy_charge();
        int ncnt = 0;
        for (int i = 0; i < N; i++)
            if (imp[i])
                ncnt++;
        if (pcnt == ncnt)
            break;
        pcnt = ncnt;
    }
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
    init(a, r, u, v);
    solve();
    vector<int> res(N);
    for (int i = 0; i < N; i++)
        res[i] = (bor[i] ? 0 : 1);
    return res;
}

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