oj.uz

Submission #57210

# Submission time Handle Problem Language Result Execution time Memory
57210 2018-07-14T09:28:11 Z Crown Toy Train (IOI17_train) C++14
5 / 100
 25 ms 2808 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< 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) 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;
    		if(all.size() == f_a.size())
    		{
    			for(auto u : all) proc[u] = true;
    			for(auto u : all) Who_wins[u] = true;
    			continue;
    		}
    		for(auto u : all)
    		{
    			if(!binary_search(f_a.begin(), f_a.end(), u)) x.pb(u); 
    		}
    		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> 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 11 ms 1912 KB Output is correct
2 Correct 17 ms 1912 KB Output is correct
3 Correct 16 ms 1912 KB Output is correct
4 Correct 10 ms 1912 KB Output is correct
5 Correct 10 ms 1912 KB Output is correct
6 Correct 10 ms 1912 KB Output is correct
7 Correct 12 ms 1912 KB Output is correct
8 Correct 11 ms 1912 KB Output is correct
9 Correct 12 ms 1912 KB Output is correct
10 Correct 11 ms 1948 KB Output is correct
11 Correct 11 ms 2168 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2808 KB Output is correct
2 Correct 16 ms 2808 KB Output is correct
3 Correct 23 ms 2808 KB Output is correct
4 Incorrect 25 ms 2808 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 2808 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 Correct 11 ms 1912 KB Output is correct
2 Correct 17 ms 1912 KB Output is correct
3 Correct 16 ms 1912 KB Output is correct
4 Correct 10 ms 1912 KB Output is correct
5 Correct 10 ms 1912 KB Output is correct
6 Correct 10 ms 1912 KB Output is correct
7 Correct 12 ms 1912 KB Output is correct
8 Correct 11 ms 1912 KB Output is correct
9 Correct 12 ms 1912 KB Output is correct
10 Correct 11 ms 1948 KB Output is correct
11 Correct 11 ms 2168 KB Output is correct
12 Incorrect 2 ms 2168 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -