oj.uz

Submission #56634

# Submission time Handle Problem Language Result Execution time Memory
56634 2018-07-12T04:02:31 Z Crown Toy Train (IOI17_train) C++14
0 / 100
 16 ms 2388 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;

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

stack<int> s;
vector<bool> vis;
vector<int> comp;
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;
}

void dfs3(int u)
{
	mark[u] = true;
	for(auto v : scc_rev[u])
	{
		if(mark[u]) 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();
	for(int i = 0; i< m; i++)
	{
		adj[u[i]].pb(v[i]);
		rev[v[i]].pb(u[i]);
	}
	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])
		{
			has_charge[comp[u]] = true;
		}
	}
	vis.assign(n+1, 0);
	for(int u = 1; u<= compcount; u++)
	{
		if(has_charge[u] == a[0] && !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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1912 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 2 ms 1912 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 16 ms 2388 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 12 ms 2388 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 13 ms 2388 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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