Submission #1015385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015385		hotboy2703	Toy Train (IOI17_train)	C++17	100 / 100	220 ms	1284 KiB

train

#include "train.h"

#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 5e3+10;
vector <ll> g[MAXN];
ll cnt[MAXN];
ll sus[MAXN];
bool in[MAXN];
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
    ll n =  sz(a);
    for (ll i = 0;i < sz(u);i ++){g[v[i]].push_back(u[i]);cnt[u[i]]++;sus[u[i]]++;}
    vector <ll> res(n,-1);
    while (1){
        vector <ll> R;
        for (ll i = 0;i < n;i ++){
            if (res[i] == -1 && r[i])R.push_back(i);
        }
        if (sz(R)==0){
            for (ll i = 0;i < n;i ++){
                if (res[i] == -1)res[i] = 0;
            }
            break;
        }
        for (auto x:R)in[x] = 1;
        for (ll i = 0;i < n;i ++)if (res[i] != -1)in[i] = 1;
        ll ptr = 0;
        while (ptr < sz(R)){
            ll u = R[ptr];
            ptr++;
            for (auto v:g[u]){
                if (!a[v])cnt[v]--;
                if (in[v])continue;
                if (a[v]){
                    in[v] = 1;
                    R.push_back(v);
                }
                else {
                    if (cnt[v]==0){in[v] = 1;R.push_back(v);}
                }
            }
        }
        vector <ll> X;
        for (ll i = 0;i < n;i ++){
            if (res[i] == -1 && !in[i]){X.push_back(i);}
        }
        if (sz(X)==0){
            for (auto u:R){
                res[u] = 1;
            }
            break;
        }
        for (ll i = 0;i < n;i ++){
            in[i] = 0;
            cnt[i] = sus[i];
        }

        R=X;
        for (auto x:R)in[x] = 1;
        for (ll i = 0;i < n;i ++)if (res[i] != -1)in[i] = 1;
        ptr = 0;
        while (ptr < sz(R)){
            ll u = R[ptr];
            ptr++;
            for (auto v:g[u]){
                if (a[v])cnt[v]--;
                if (in[v])continue;
                if (!a[v]){
                    in[v] = 1;
                    R.push_back(v);
                }
                else {
                    if (cnt[v]==0){in[v] = 1;R.push_back(v);}
                }
            }
        }
        for (auto x:R){
            res[x] = 0;
            for (auto v:g[x])sus[v]--;
        }

        for (ll i = 0;i < n;i ++){
            in[i] = 0;
            cnt[i] = sus[i];
        }

    }
	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