Submission #1015307

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1015307	2024-07-06T08:35:37 Z	hotboy2703	Toy Train (IOI17_train)	C++17	0 / 100	48 ms	1628 KB

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];
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[u[i]].push_back(v[i]);cnt[v[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);
                in[i] = 1;
            }
        }
        if (sz(R)==0){
            for (ll i = 0;i < n;i ++){
                res[i] = 0;
                break;
            }
        }
        ll ptr = 0;
        while (ptr < sz(R)){
            ll u = R[ptr];
            ptr++;
            for (auto v:g[u]){
                if (in[v])continue;
                if (a[v]){
                    in[v] = 1;
                    R.push_back(v);
                }
                else {
                    cnt[v]--;
                    if (cnt[v]==0){in[v] = 1;R.push_back(v);}
                }
            }
        }
//        for (auto x:R)cout<<x<<' ';
//        cout<<endl;
        vector <ll> X;
        for (ll i = 0;i < n;i ++){
            if (res[i] == -1 && !in[i]){X.push_back(i);in[i] = 1;}
        }
        if (sz(X)==0){
            for (auto u:R){
                res[u] = 1;
            }
            break;
        }
        for (auto u:R){
            in[u] = 0;
            for (auto v:g[u]){
                if (!a[v])cnt[v]++;
            }
        }
        R=X;
        ptr = 0;
        while (ptr < sz(R)){
            ll u = R[ptr];
            ptr++;
            for (auto v:g[u]){
                if (in[v])continue;
                if (!a[v]){
                    in[v] = 1;
                    R.push_back(v);
                }
                else {
                    cnt[v]--;
                    if (cnt[v]==0){in[v] = 1;R.push_back(v);}
                }
            }
        }
        for (auto u:R){
            res[u] = 0;
            in[u] = 0;
            for (auto v:g[u]){
                if (a[v])cnt[v]++;
            }
        }
    }
	return res;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	860 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	1372 KB	Output is correct
2	Correct	27 ms	1368 KB	Output is correct
3	Correct	48 ms	1628 KB	Output is correct
4	Incorrect	9 ms	1372 KB	3rd lines differ - on the 13th token, expected: '1', found: '0'
5	Halted	0 ms	0 KB	-