oj.uz

Submission #301609

# Submission time Handle Problem Language Result Execution time Memory
301609 2020-09-18T05:18:31 Z TMJN Toy Train (IOI17_train) C++17
0 / 100
 11 ms 3328 KB 
#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[x]=x;
}

void dfs(int x){
	if(vis[x])return;
	vis[x]=true;
	for(int i:E[x]){
		dfs(i);
	}
	ord[x]=c;
	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]);
	}
	assert(false);
	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);
		}
	}
	vector<int>winner(N,0);
	for(int i=0;i<N;i++){
		winner[i]=B[par(i)];
	}
	return winner;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 2176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 3328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 2560 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 2816 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 2176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -