oj.uz

답안 #57185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57185 2018-07-14T08:43:39 Z Crown 장난감 기차 (IOI17_train) C++14
15 / 100
 2000 ms 9660 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];
set<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] = 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 : bic[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);
		bic[u].insert(v); bic[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) printf("%d ", u); printf("\n");
		// for(auto u : charge) printf("c%d ", u); printf("\n");
		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);
			}
			for(auto v : bic[u])
			{
				bic[v].erase(u);
			}
			bic[u].clear();
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 2936 KB Output is correct
2 Correct 13 ms 3000 KB Output is correct
3 Correct 18 ms 3032 KB Output is correct
4 Correct 23 ms 3180 KB Output is correct
5 Correct 19 ms 3356 KB Output is correct
6 Correct 14 ms 3404 KB Output is correct
7 Correct 17 ms 3616 KB Output is correct
8 Correct 15 ms 3616 KB Output is correct
9 Correct 22 ms 3660 KB Output is correct
10 Correct 19 ms 3740 KB Output is correct
11 Correct 13 ms 3740 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3740 KB Output is correct
2 Correct 2 ms 3740 KB Output is correct
3 Correct 3 ms 3740 KB Output is correct
4 Correct 3 ms 3740 KB Output is correct
5 Correct 3 ms 3740 KB Output is correct
6 Correct 3 ms 3740 KB Output is correct
7 Correct 3 ms 3740 KB Output is correct
8 Correct 3 ms 3740 KB Output is correct
9 Correct 4 ms 3740 KB Output is correct
10 Correct 3 ms 3740 KB Output is correct
11 Correct 3 ms 3740 KB Output is correct
12 Correct 4 ms 3740 KB Output is correct
13 Correct 5 ms 3740 KB Output is correct
14 Correct 4 ms 3740 KB Output is correct
15 Correct 4 ms 3740 KB Output is correct
16 Correct 4 ms 3740 KB Output is correct
17 Correct 3 ms 3740 KB Output is correct
18 Correct 3 ms 3740 KB Output is correct
19 Correct 3 ms 3740 KB Output is correct
20 Correct 3 ms 3740 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1972 ms 7284 KB Output is correct
2 Execution timed out 2047 ms 7492 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 7492 KB Output is correct
2 Correct 38 ms 7492 KB Output is correct
3 Correct 52 ms 8168 KB Output is correct
4 Correct 48 ms 8376 KB Output is correct
5 Correct 87 ms 8612 KB Output is correct
6 Correct 47 ms 8660 KB Output is correct
7 Execution timed out 2061 ms 8860 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 9316 KB Output is correct
2 Correct 41 ms 9388 KB Output is correct
3 Correct 43 ms 9660 KB Output is correct
4 Correct 45 ms 9660 KB Output is correct
5 Execution timed out 2035 ms 9660 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 2936 KB Output is correct
2 Correct 13 ms 3000 KB Output is correct
3 Correct 18 ms 3032 KB Output is correct
4 Correct 23 ms 3180 KB Output is correct
5 Correct 19 ms 3356 KB Output is correct
6 Correct 14 ms 3404 KB Output is correct
7 Correct 17 ms 3616 KB Output is correct
8 Correct 15 ms 3616 KB Output is correct
9 Correct 22 ms 3660 KB Output is correct
10 Correct 19 ms 3740 KB Output is correct
11 Correct 13 ms 3740 KB Output is correct
12 Correct 3 ms 3740 KB Output is correct
13 Correct 2 ms 3740 KB Output is correct
14 Correct 3 ms 3740 KB Output is correct
15 Correct 3 ms 3740 KB Output is correct
16 Correct 3 ms 3740 KB Output is correct
17 Correct 3 ms 3740 KB Output is correct
18 Correct 3 ms 3740 KB Output is correct
19 Correct 3 ms 3740 KB Output is correct
20 Correct 4 ms 3740 KB Output is correct
21 Correct 3 ms 3740 KB Output is correct
22 Correct 3 ms 3740 KB Output is correct
23 Correct 4 ms 3740 KB Output is correct
24 Correct 5 ms 3740 KB Output is correct
25 Correct 4 ms 3740 KB Output is correct
26 Correct 4 ms 3740 KB Output is correct
27 Correct 4 ms 3740 KB Output is correct
28 Correct 3 ms 3740 KB Output is correct
29 Correct 3 ms 3740 KB Output is correct
30 Correct 3 ms 3740 KB Output is correct
31 Correct 3 ms 3740 KB Output is correct
32 Correct 1972 ms 7284 KB Output is correct
33 Execution timed out 2047 ms 7492 KB Time limit exceeded
34 Halted 0 ms 0 KB -