oj.uz

Submission #57204

# Submission time Handle Problem Language Result Execution time Memory
57204 2018-07-14T09:16:28 Z Crown Toy Train (IOI17_train) C++14
0 / 100
 28 ms 2636 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;
vector<int> adj[maxn];
vector<int> rev[maxn];
vector<int> bic[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] = 0;
		for(auto v : adj[u])
		{
			if(!proc[v]) out[u]++;
		}
	}	
	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] || proc[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 : bic[u])
		if(!vis[v] && !proc[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].pb(v); rev[v].pb(u);
		bic[u].pb(v); bic[v].pb(u);
	}
	queue< 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(i);
	}
	while(!Q.empty())
	{
		int u = Q.front(); Q.pop();
		vector<int> all, charge;
		dfs(u, all, charge);		// for(auto u : all) printf("%d ", u); printf("\n");
		// for(auto u : charge) printf("c%d ", u); printf("\n");
		vector<int> f_a = f(1, all, charge);
		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)
		{
			proc[u] = 1;
		}
		for(auto u : all) vis[u] = false;
		for(auto u : all)
		{
			if(vis[u] || proc[u]) continue;
			vis[u] = true;
			vector<int> fuck1, fuck2;
			dfs(u, fuck1, fuck2);
			//for(auto u : All) printf("**%d ", u); printf("\n");
			//for(auto u : Charge) printf("***%d ", u); printf("\n");
			Q.push(u);
		}
	}
	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 Incorrect 9 ms 1784 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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