제출 #613614

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
613614		rrrr10000	장난감 기차 (IOI17_train)	C++14	11 / 100	648 ms	1788 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_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
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51