oj.uz

Submission #57177

# Submission time Handle Problem Language Result Execution time Memory
57177 2018-07-14T08:20:26 Z Crown Toy Train (IOI17_train) C++14
5 / 100
 505 ms 3904 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> &all, vector<int> s)
{
	for(auto u : all)
	{
		inq[u] = 0;
		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(auto u : all) if(inq[u]) res.pb(u);
	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;
		vis[i] = true;
		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, all, 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, all, x);
		for(auto u : f_b)
		{
			for(auto v : adj[u])
			{
				rev[v].erase(u);
			}
			for(auto v : rev[u])
			{
				adj[v].erase(u);
			}
			adj[u].clear(); 
			rev[u].clear();
			proc[u] = 1;
		}
		//for(auto u : f_b) printf("f_b%d ", u); printf("\n");
		for(auto u : all)
		{
			if(vis[u] || proc[u]) continue;
			vis[u] = true;
			vector<int> All, Charge;
			dfs(u, All, Charge);
			//for(auto u : All) printf("**%d ", u); printf("\n");
			//for(auto u : Charge) printf("***%d ", u); printf("\n");
			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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2132 KB Output is correct
2 Correct 13 ms 2132 KB Output is correct
3 Correct 16 ms 2132 KB Output is correct
4 Correct 10 ms 2132 KB Output is correct
5 Correct 14 ms 2132 KB Output is correct
6 Correct 10 ms 2132 KB Output is correct
7 Correct 12 ms 2132 KB Output is correct
8 Correct 11 ms 2156 KB Output is correct
9 Correct 12 ms 2172 KB Output is correct
10 Correct 13 ms 2192 KB Output is correct
11 Correct 15 ms 2368 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2368 KB 3rd lines differ - on the 8th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 3772 KB Output is correct
2 Correct 505 ms 3900 KB Output is correct
3 Incorrect 497 ms 3900 KB 3rd lines differ - on the 9th token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 3900 KB 3rd lines differ - on the 21st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 3904 KB 3rd lines differ - on the 15th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2132 KB Output is correct
2 Correct 13 ms 2132 KB Output is correct
3 Correct 16 ms 2132 KB Output is correct
4 Correct 10 ms 2132 KB Output is correct
5 Correct 14 ms 2132 KB Output is correct
6 Correct 10 ms 2132 KB Output is correct
7 Correct 12 ms 2132 KB Output is correct
8 Correct 11 ms 2156 KB Output is correct
9 Correct 12 ms 2172 KB Output is correct
10 Correct 13 ms 2192 KB Output is correct
11 Correct 15 ms 2368 KB Output is correct
12 Incorrect 2 ms 2368 KB 3rd lines differ - on the 8th token, expected: '0', found: '1'
13 Halted 0 ms 0 KB -