Submission #56638

#	Time	Username	Problem	Language	Result	Execution time	Memory
56638		Crown	Toy Train (IOI17_train)	C++14	11 / 100	23 ms	4952 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 5005;

vector<int> adj[maxn];
vector<int> rev[maxn];
vector<int> scc[maxn];
vector<int> scc_rev[maxn];
int has_charge[maxn];
int mark[maxn];
int scc_sz[maxn];

stack<int> s;
vector<bool> vis;
vector<int> comp;
vector<int> loop;

void dfs(int u)
{
	vis[u] = true;
	for(auto v : adj[u])
	{
		if(vis[v]) continue;
		dfs(v);
	}
	s.push(u);
}

int compcount = 0;

void dfs2(int u)
{
	vis[u] = true;
	for(auto v : rev[u])
	{
		if(vis[v]) continue;
		dfs2(v);
	}
	s.push(u);
	comp[u] = compcount;
	scc_sz[compcount]++;
}

void dfs3(int u)
{
	mark[u] = true;
	for(auto v : scc_rev[u])
	{
		if(mark[v]) continue;
		dfs3(v);
	}
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
	int n = a.size(); int m = u.size();
	loop.resize(n);
	for(int i = 0; i< m; i++)
	{
		adj[u[i]].pb(v[i]);
		rev[v[i]].pb(u[i]);
		if(u[i] == v[i]) 
			loop[u[i]] = true;
	}
	vis.assign(n, 0);
	for(int i = 0; i< n; i++) 
	{
		if(!vis[i]) dfs(i);
	}	
	comp.resize(n);
	vis.assign(n, 0);
	while(!s.empty())
	{
		int u = s.top(); s.pop();
		if(comp[u]) continue;
		compcount++;
		dfs2(u);
	}
	for(int u = 0; u< n; u++)
	{
		for(auto v : adj[u])
		{
			if(comp[u] == comp[v]) continue;
			scc[comp[u]].pb(comp[v]);
			scc_rev[comp[v]].pb(comp[u]);
		}
	}
	for(int u = 1; u<= compcount; u++)
	{
		sort(scc[u].begin(), scc[u].end());
		scc[u].resize(unique(scc[u].begin(), scc[u].end())-scc[u].begin());
		sort(scc_rev[u].begin(), scc_rev[u].end());
		scc_rev[u].resize(unique(scc_rev[u].begin(), scc_rev[u].end())-scc_rev[u].begin());
	}
	for(int u = 0; u< n; u++)
	{
		if(r[u] && (scc_sz[comp[u]]>= 2 || loop[u]))
		{
			has_charge[comp[u]] = true;
		}
	}
	vis.assign(n+1, 0);
	for(int u = 1; u<= compcount; u++)
	{
		if(has_charge[u] && !mark[u])
		{
			dfs3(u);
		}
	}
	vector<int> res(n);
	for(int u = 0; u< n; u++)
	{
		if(a[0])
			res[u] = mark[comp[u]];
		else 
			res[u] = 1-mark[comp[u]];
	}
	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