Submission #133753

#	Time	Username	Problem	Language	Result	Execution time	Memory
133753		dvdg6566	Toy Train (IOI17_train)	C++14	11 / 100	1025 ms	1840 KiB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define pb emplace_back
#define mp make_pair
#define MAXN 5010
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()

vi res;
vi U[MAXN],V[MAXN];
vi stat;
int vis[MAXN];
vi bad;
int outdeg[MAXN];
int A[MAXN];
int N;

void dfs(int x){
	for (auto v : V[x])if (vis[v]==0){
		vis[v] = 1;
		dfs(v);
	}
}

queue<int> q;
int done[MAXN];

void dest(int x){
	done[x]=1;
	q.push(x);
	while(SZ(q)){
		int t = q.front();q.pop();
		res[t]=1;
		// cout<<"Remove "<<t<<'\n';
		for (auto i : U[t])if(!done[i]){
			if (A[i] == 1){
				// A owns it then can just remove
				q.push(i);
				// cout<<"Push "<<i<<'\n';
				done[i]=1;
			}else{
				--outdeg[i];
				if (outdeg[i] == 0){q.push(i);done[i]=1;}
				// cout<<"Current outdeg node "<<i<< " is "<<outdeg[i]<<'\n';
			}
		}
	}
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	N = SZ(a);
	res.resize(N,0);
	for (int i=0;i<N;++i)A[i] = a[i];
	int m = SZ(u);
	for (int i=0;i<m;++i){
		V[u[i]].pb(v[i]);
		U[v[i]].pb(u[i]);
		// cout<<"Appending "<<u[i]<<" to "<<v[i]<<'\n';
		++outdeg[u[i]];
	}
	for (int i=0;i<N;++i)if(r[i])stat.pb(i);
	for (auto i : stat){
		memset(vis,0,sizeof(vis));
		dfs(i);
		if (vis[i]){
			// This station is an exit point 
			bad.pb(i);
		}
	}
	for (auto i : bad){
		dest(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