Submission #613614

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
613614	2022-07-30T07:53:37 Z	rrrr10000	Toy Train (IOI17_train)	C++14	11 / 100	648 ms	1788 KB

train

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
typedef tuple<ll,ll,ll> PP;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pb emplace_back
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001001001001;
#include "train.h"

std::vector<int> who_wins4(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
    ll n=a.size();
    vvi g(n),rg(n);
    rep(i,u.size()){
        g[u[i]].pb(v[i]);
        rg[v[i]].pb(u[i]);
    }
    vb flag(n,false);
    queue<ll> que;
    rep(s,n)if(r[s]){
        flag[s]=true;que.push(s);
    }
    vi cnt_out(n);
    rep(i,n)cnt_out[i]=g[i].size();
    while(!que.empty()){
        ll i=que.front();que.pop();
        for(ll x:rg[i])if(!flag[x]){
            cnt_out[x]--;
            if(a[x]==1||cnt_out[x]==0){
                flag[x]=true;que.push(x);
            }
        }
    }
    rep(s,n)if(!flag[s])que.push(s);
    rep(i,n)cnt_out[i]=g[i].size();
    while(!que.empty()){
        ll i=que.front();que.pop();
        for(ll x:rg[i])if(flag[x]){
            cnt_out[x]--;
            if(a[x]==0||cnt_out[x]==0){
                flag[x]=false;que.push(x);
            }
        }
    }
	vector<int> res(a.size());
    rep(i,n)res[i]=flag[i];
    return res;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
    ll n=a.size();
    vvi g(n),rg(n);
    rep(i,u.size()){
        g[u[i]].pb(v[i]);
        rg[v[i]].pb(u[i]);
    }
    vb flag(n,false);
    rep(s,n)if(r[s]){
        vb tmp(n,false);
        queue<ll> que;que.push(s);
        while(!que.empty()){
            ll i=que.front();que.pop();
            for(ll x:g[i])if(!tmp[x]){
                tmp[x]=true;que.push(x);
            }
        }
        if(tmp[s])flag[s]=true;
    }
    queue<ll> que;
    rep(i,n)if(flag[i])que.push(i);
    while(!que.empty()){
        ll i=que.front();que.pop();
        for(ll x:rg[i])if(!flag[x]){
            flag[x]=true;que.push(x);
        }
    }
	vector<int> res(a.size());
    rep(i,n)res[i]=flag[i];
    return res;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	108 ms	1012 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	212 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	1492 KB	Output is correct
2	Correct	25 ms	1748 KB	Output is correct
3	Correct	44 ms	1620 KB	Output is correct
4	Correct	231 ms	1748 KB	Output is correct
5	Correct	35 ms	1788 KB	Output is correct
6	Correct	66 ms	1772 KB	Output is correct
7	Correct	220 ms	1740 KB	Output is correct
8	Correct	8 ms	1716 KB	Output is correct
9	Correct	7 ms	1620 KB	Output is correct
10	Correct	9 ms	1588 KB	Output is correct
11	Correct	8 ms	1620 KB	Output is correct
12	Correct	8 ms	1608 KB	Output is correct
13	Correct	8 ms	1756 KB	Output is correct
14	Correct	8 ms	1756 KB	Output is correct
15	Correct	9 ms	1756 KB	Output is correct
16	Correct	8 ms	1788 KB	Output is correct
17	Correct	9 ms	1748 KB	Output is correct
18	Correct	116 ms	1192 KB	Output is correct