oj.uz

Submission #57165

# Submission time Handle Problem Language Result Execution time Memory
57165 2018-07-14T07:51:15 Z Crown Toy Train (IOI17_train) C++14
0 / 100
 2000 ms 32844 KB 
#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;

int out[maxn];
int inq[maxn];
int proc[maxn];
int Who_wins[maxn];
bool vis[maxn];

vector<int> A;
vector<int> R;
set<int> adj[maxn];
set<int> rev[maxn];
vector<int> U, V;

int n, m;

vector<int> f(int is_a, vector<int> s)
{
	memset(inq, 0, sizeof inq);
	for(int u = 0; u< n; u++)
	{
		out[u] = adj[u].size();
	}	
	queue<int> q;
	for(auto u : s)
	{
		inq[u] = true;
		q.push(u);
	}
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(auto v : rev[u])
		{
			if(inq[v]) continue;
			out[v]--;
			if(A[v] == is_a)
			{
				inq[v] = true;
				q.push(v);
			}
			else if(out[v] == 0)
			{
				inq[v] = true;
				q.push(v);
			}
		}
	}
	vector<int> res;
	for(int i = 0; i< n; i++) if(inq[i]) res.pb(i);
	return res;
}

void dfs(int u, vector<int> &all, vector<int> &charge)
{
	all.pb(u); 
	if(R[u]) charge.pb(u);
	for(auto v : adj[u])
		if(!vis[v])
		{
			vis[v] = true;
			dfs(v, all, charge);
		}
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> _U, vector<int> _V)
{
	A = a; R = r;
	U = _U; V = _V;
	n = a.size(), m = _U.size();
	for(int i = 0; i< m; i++)
	{
		int u = _U[i], v = _V[i];
		adj[u].insert(v); rev[v].insert(u);
	}
	queue< pair<vector<int>, vector<int> > > Q;
	for(int i = 0; i< n; i++)
	{
		if(vis[i]) continue;
		vector<int> all, charge;
		dfs(i, all, charge);
		Q.push(make_pair(all, charge));
	}
	while(!Q.empty())
	{
		vector<int> all = Q.front().X, charge = Q.front().Y; Q.pop();
		for(auto u : all) vis[u] = false;
		vector<int> f_a = f(1, charge);
		sort(f_a.begin(), f_a.end());
		vector<int> x;
		for(auto u : all)
		{
			if(!binary_search(f_a.begin(), f_a.end(), u)) x.pb(u); 
		}
		if(x.empty())
		{
			for(auto u : all) proc[u] = true;
			for(auto u : all) Who_wins[u] = true;
			continue;
		}
		vector<int> f_b = f(0, x);
		for(auto u : f_b)
		{
			for(auto v : adj[u])
			{
				rev[v].erase(u);
			}
			for(auto v : rev[u])
			{
				adj[u].erase(v);
			}
			adj[u].clear(); 
			proc[u] = 1;
		}
		for(auto u : all)
		{
			if(vis[u]) continue;
			vector<int> all, cahrge;
			dfs(u, all, charge);
			Q.push(make_pair(all, charge));
		}
	}
	vector<int> res(n);
	for(int i = 0; i< n; i++) res[i] = Who_wins[i];
	return res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 32844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 32844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 32844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 32844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 32844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 32844 KB Time limit exceeded
2 Halted 0 ms 0 KB -