Submission #301626

#	Time	Username	Problem	Language	Result	Execution time	Memory
301626		TMJN	Toy Train (IOI17_train)	C++17	0 / 100	11 ms	2816 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

int N,M,ord[5000],c,T[5000];
vector<int>E[5000],R[5000],V[5000];
bool vis[5000],B[5000];

int par(int x){
	if(T[x]<0)return x;
	return T[x]=par(T[x]);
}

void uni(int x,int y){
	x=par(x);
	y=par(y);
	if(x==y)return;
	T[x]+=T[y];
	T[y]=x;
}

void dfs(int x){
	if(vis[x])return;
	vis[x]=true;
	for(int i:E[x]){
		dfs(i);
	}
	ord[c]=x;
	c++;
}

void dfs2(int x,int y){
	if(vis[x])return;
	vis[x]=true;
	uni(x,y);
	for(int i:R[x]){
		dfs2(i,y);
	}
}

void dfs3(int x){
	if(vis[x])return;
	vis[x]=true;
	for(int i:V[x]){
		dfs3(i);
		B[x]|=B[i];
	}
}

vector<int> who_wins(vector<int>a,vector<int>r,vector<int>u,vector<int>v){
	N=a.size();
	M=u.size();
	for(int i=0;i<M;i++){
		E[u[i]].push_back(v[i]);
		R[v[i]].push_back(u[i]);
	}
	for(int i=0;i<N;i++){
		assert(a[i]==1);
		T[i]=-1;
	}
	dfs(0);
	for(int i=0;i<N;i++){
		vis[i]=false;
	}
	for(int i=N-1;i>=0;i--){
		dfs2(ord[i],ord[i]);
	}
	for(int i=0;i<N;i++){
		int p=par(i);
		if(T[p]==-1){
			for(int j:V[i]){
				if(j==i&&r[i]==1)B[i]=true;
			}
		}
		else if(r[i]==1){
			B[p]=true;
		}
	}
	for(int i=0;i<M;i++){
		V[par(u[i])].push_back(par(v[i]));
	}
	for(int i=0;i<N;i++){
		vis[i]=false;
	}
	for(int i=0;i<N;i++){
		if(T[i]<0){
			dfs3(i);
		}
	}
	for(int i=0;i<N;i++){
//		cout<<i<<' '<<ord[i]<<endl;
	}
	for(int i=0;i<N;i++){
//		cout<<i<<' '<<par(i)<<endl;
	}
	vector<int>winner(N,0);
	for(int i=0;i<N;i++){
		winner[i]=B[par(i)];
	}
	return winner;
}

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