Submission #133776

#	Time	Username	Problem	Language	Result	Execution time	Memory
133776		dvdg6566	Toy Train (IOI17_train)	C++14	0 / 100	997 ms	3548 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 V[MAXN], U[MAXN];
int lowlink[MAXN], vis[MAXN], ind[MAXN],SCC[MAXN];
int a=1,b=1,N;
int curstack[MAXN];
int A[MAXN];
stack<int> stk;
vi res;
int hg[MAXN];
int selfedge[MAXN];
 
void dfs(int x){
	if (ind[x]!=-1)return;
	ind[x] = lowlink[x] = a++;
	curstack[x]=1;
	stk.push(x);
	for (auto v : V[x]){
		if(SCC[v]!=-1)continue;
		if(ind[v] == -1){
			dfs(v);
			lowlink[x] = min(lowlink[v], lowlink[x]);
			continue;
		}else if (curstack[v]){
			lowlink[x] = min(lowlink[x],ind[v]);
		}
	}
	// cout<<x<<' '<<ind[x]<<' '<<lowlink[x]<<'\n';
	if (lowlink[x] == ind[x]){
		while(stk.top()!=x){
			curstack[stk.top()]=0;
			SCC[stk.top()] = b;
			stk.pop();
		}
		stk.pop();
		SCC[x]=b++;
	}
}
 
void dfs2(int x){
	for (auto i : U[x])if(vis[i]==0){
		vis[i] = 1;
		res[i] = 1;
		dfs2(i);
	}
}
 
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);
	memset(ind,-1,sizeof(ind));
	memset(SCC,-1,sizeof(SCC));
	for (int i=0;i<N;++i)A[i] = a[i];
	int m = SZ(u);
	for (int i=0;i<m;++i){
		U[v[i]].pb(u[i]);
		if (u[i]==v[i])selfedge[u[i]]=1;
		
		if (r[u[i]] || r[v[i]])continue;
		V[u[i]].pb(v[i]);
		// cout<<u[i]<<' '<<v[i]<<'\n';
	}
	vi mem(N,0);
	for (int i=0;i<N;++i){
		if (r[i])continue;
		if (vis[i])continue;
		dfs(i);
	}
	for (int i=0;i<N;++i)if (!r[i])hg[SCC[i]]++;
	// for (int i=0;i<N;++i)cout<<SCC[i]<<' ';cout<<'\n';
	for (int i=0;i<N;++i)if(r[i]){
		if (hg[SCC[i]] == 1){
			if (!selfedge[i])continue;
		}
		mem[SCC[i]] = 1;
	}
	for (int i=0;i<N;++i)if(mem[SCC[i]]){
		memset(vis,0,sizeof(vis));
		vis[i]=1;
		dfs2(i);
	}
 
	return res;
}

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