제출 #613619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
613619		rrrr10000	장난감 기차 (IOI17_train)	C++14	100 / 100	537 ms	1892 KiB

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_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);
    while(true){
        rep(i,n)flag[i]=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();
        bool upd=false;
        while(!que.empty()){
            ll i=que.front();que.pop();
            if(r[i]==1){
                upd=true;r[i]=0;
            }
            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);
                }
            }
        }
        if(!upd)break;
    }
	vector<int> res(a.size());
    rep(i,n)res[i]=flag[i];
    return res;
}
std::vector<int> who_wins3(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;
}
/*
int main(){
    rep(tt,10000){
        ll n=rand()%5+2;
        vector<int> u,v;
        rep(i,n){
            ll k=rand()%n+1;
            set<ll> S;
            rep(j,k){
                S.insert(rand()%n);
            }
            for(ll x:S){
                u.pb(i);v.pb(x);
            }
        }
        vector<int> a(n),r(n);
        rep(i,n)a[i]=1;
        rep(i,n)r[i]=rand()%2;
        r[0]=1;
        vector<int> res3=who_wins3(a,r,u,v);
        vector<int> res4=who_wins4(a,r,u,v);
        if(res3!=res4){
            out(tt);
            outv(a);outv(r);outv(u);outv(v);
            outv(res3);outv(res4);break;
        }
    }
}
*/

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