Submission #358548

#	Time	Username	Problem	Language	Result	Execution time	Memory
358548		Kerim	Toy Train (IOI17_train)	C++17	16 / 100	216 ms	11756 KiB

train

#include "train.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int col[MAXN],vis[MAXN],res,n,m;
vector<int>adj[MAXN],inv[MAXN],ans;
bool dfs(int nd,int root){
	if(vis[nd])return (nd==root);
	vis[nd]=1;
	tr(it,adj[nd])
		if(dfs(*it,root))return 1;
	return 0;
}
bool dfs2(int nd,int root){
	if(col[nd])return 0;
	if(vis[nd])return (nd==root);
	vis[nd]=1;
	tr(it,adj[nd])
		if(dfs(*it,root))return 1;
	return 0;
}
void dfs1(int nd,int sen){
	if(ans[nd]==sen)return;
	ans[nd]=sen;
	tr(it,inv[nd])
		dfs1(*it,sen);	
}
int same[MAXN],go[MAXN],who[MAXN];
vector<int> who_wins(vector<int> a, vector<int> r,vector<int> u,vector<int> v) {
	n=int(a.size());m=int(u.size());
	for(int i=0;i<n;i++)col[i]=r[i],who[i]=a[i];
	int subtask3=1,subtask4=1,subtask1=1;
	for(int i=0;i<n;i++)subtask3&=(a[i]),subtask4&=(!a[i]);
	ans.resize(n);for(int i=0;i<n;i++)ans[i]=0;
	for(int i=0;i<m;i++)
		adj[u[i]].pb(v[i]),inv[v[i]].pb(u[i]),subtask1&=(v[i]==u[i] or v[i]==u[i]+1);
	if(subtask1){
		for(int i=0;i<n;i++)
			tr(it,adj[i])
				same[i]|=(*it==i),go[i]|=(*it==i+1);
		for(int i=0;i<n;i++){
			int j=i;
			while(1){
				if(same[j] and col[j]==a[j]){
					ans[i]=a[j];
					break;
				}
				if(go[j])
					j++;
				else{
					if(col[j] and same[j])
						ans[i]=1;
					break;
				}
			}
		}
	}
	else if(subtask3){
		for(int i=0;i<n;i++)
			if(col[i]){
				for(int j=0;j<n;j++)vis[j]=0;
				int ret=dfs(i,i);
				if(ret)
					dfs1(i,1);
			}
	}
	else if(subtask4){
		for(int i=0;i<n;i++)ans[i]=1;
		for(int i=0;i<n;i++)
			if(!col[i]){
				for(int j=0;j<n;j++)vis[j]=0;
				int ret=dfs2(i,i);
				if(ret)
					dfs1(i,0);
			}
	}
	else assert(0);
	return ans;
}

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