oj.uz

Submission #45482

# Submission time Handle Problem Language Result Execution time Memory
45482 2018-04-14T11:40:56 Z Abelyan Toy Train (IOI17_train) C++14
11 / 100
 47 ms 2304 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 5006;
int n, m;
vector<int> g[N],ing[N];
bool col[N],chrg[N];
unordered_set <int> R;

unordered_set<int> rev(unordered_set<int> &s){
	unordered_set<int> ans;
	for (int i = 0; i < n; i++){
		if (s.count(i) == 0) ans.insert(i);
	}
	return ans;
}
unordered_set<int> fa(unordered_set<int> &s){
	unordered_set<int> ans;
	queue<int> q;
	for (auto k : s){
		q.push(k);
		ans.insert(k);
	}
	while (!q.empty()){
		int v = q.front();
		q.pop();
		for (auto to : ing[v]){
			if (ans.count(to)) continue;
			bool mb = true;
			for (auto k : g[to]){
				mb &= ans.count(k) == 1;
			}
			if (col[to] || mb){
				ans.insert(to);
				q.push(to);
			}
		}
	}
	return ans;
}

unordered_set<int> fb(unordered_set<int> &s){
	unordered_set<int> ans;
	queue<int> q;
	for (auto k : s){
		q.push(k);
		ans.insert(k);
	}
	while (!q.empty()){
		int v = q.front();
		q.pop();
		for (auto to : ing[v]){
			if (ans.count(to)==1) continue;
			bool mb = true;
			for (auto k : g[to]){
				mb &= ans.count(k) == 1;
			}
			if (!col[to] || mb){
				ans.insert(to);
				q.push(to);
			}
		}
	}
	return ans;
}

unordered_set<int> intersect(unordered_set<int> &a, unordered_set<int> &b){
	unordered_set<int> ans;
	for (auto i : a){
		if (b.count(i)) ans.insert(i);
	}
	return ans;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n = a.size();
	m = u.size();
	for (int i = 0; i < m; i++){
		g[u[i]].push_back(v[i]);
		ing[v[i]].push_back(u[i]);
	}
	for (int i = 0; i < n; i++){
		if (a[i]){
			col[i] = true;
		}
	}
	for (int i = 0; i < n; i++){
		if (r[i]) chrg[i] = true;
	}
	while (1){
		for (int i = 0; i < n; i++){
			if (chrg[i]) R.insert(i);
		}
		unordered_set <int>  far = fa(R),gg=rev(far),x = fb(gg), ht = intersect(far, x);
		bool mb = false;
		for (auto k : ht){
			if (chrg[k]) mb = true, chrg[k] = false;
		}
		if (!mb){
			vector<int> ans(n,1);
			for (auto k : x){
				ans[k] = 0;
			}
			return ans;
		}
	}
}
/*
2 4 
0 1 
1 0 
0 0 
0 1 
1 0 
1 1 

*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1556 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 Correct 2 ms 1556 KB Output is correct
2 Correct 2 ms 1556 KB Output is correct
3 Correct 2 ms 1556 KB Output is correct
4 Incorrect 2 ms 1556 KB 3rd lines differ - on the 4th token, expected: '0', found: '1'
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1868 KB Output is correct
2 Correct 20 ms 1868 KB Output is correct
3 Correct 29 ms 2024 KB Output is correct
4 Correct 25 ms 2304 KB Output is correct
5 Correct 32 ms 2304 KB Output is correct
6 Correct 35 ms 2304 KB Output is correct
7 Correct 28 ms 2304 KB Output is correct
8 Correct 21 ms 2304 KB Output is correct
9 Correct 17 ms 2304 KB Output is correct
10 Correct 16 ms 2304 KB Output is correct
11 Correct 14 ms 2304 KB Output is correct
12 Correct 14 ms 2304 KB Output is correct
13 Correct 17 ms 2304 KB Output is correct
14 Correct 17 ms 2304 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2304 KB Output is correct
2 Correct 17 ms 2304 KB Output is correct
3 Correct 25 ms 2304 KB Output is correct
4 Correct 14 ms 2304 KB Output is correct
5 Correct 4 ms 2304 KB Output is correct
6 Correct 9 ms 2304 KB Output is correct
7 Correct 20 ms 2304 KB Output is correct
8 Incorrect 47 ms 2304 KB 3rd lines differ - on the 5th token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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