oj.uz

Submission #33243

# Submission time Handle Problem Language Result Execution time Memory
33243 2017-10-23T04:35:55 Z model_code Toy Train (IOI17_train) C++11
22 / 100
 2000 ms 3684 KB 
//		Red : charging station
//		Blue : not charging station

#include "train.h"
#include <iostream>
#include <vector>
#include <cstring>
#include <set>

using namespace std;

const int max_n = 5000;
const bool A = true;
const bool B = false;

int n;
std::vector <int> a[max_n], b[max_n];
bool owners[max_n];
int rem[max_n];

set <int> fill_followers(set <int> sources, bool player) {
	//cerr << "FILL [";
	//for (auto x : sources) cerr << x << ' ';
	//cerr << "] " << player << endl;
	memset (rem, 0, sizeof rem);
	set <int> res(sources);
	vector <int> queue;
	for (int i = 0; i < n; i++) if (sources.count(i) == 0) {
		rem[i] = a[i].size();
		if (owners[i] == player) rem[i] = min(rem[i], 1);
		for (auto adj : a[i]) if (sources.count(adj) > 0) rem[i] = max(0, rem[i] - 1);
		//cerr << " @rem " << i << " = " << rem[i] << endl;
		//if (rem[i] == 0) cerr << " ~ " << i << endl;
		if (rem[i] == 0) queue.push_back(i);
	}

	for (int i = 0; i < (int)queue.size(); i++) {
		int k = queue[i];
		//cerr << "BFS " << k << endl;
		res.insert(k);
		for (auto adj : b[k]) if (rem[adj] > 0) {
			rem[adj] = max(0, rem[adj] - 1);
			//cerr << " @rem " << adj << " = " << rem[adj] << endl;
			//if (rem[adj] == 0) cerr << " ~ " << adj << endl;
			if (rem[adj] == 0) queue.push_back(adj);
		}
	}

	return res;
}

vector <int> who_wins(vector <int> owner, vector <int> r, vector <int> from, vector <int> to)
{
	n = owner.size();
	int m = from.size();
	vector <int> red;
	for(int i = 0; i < n; i++)
		if(r[i])
			red.push_back(i);

	for (int i = 0; i < m; i++)
		a[from[i]].push_back(to[i]),
		b[to[i]].push_back(from[i]);
	for (int i = 0; i < n; i++)
		owners[i] = owner[i];

	set <int> sources;
	int k = red.size();
	for (int i = 0; i < k; i++) sources.insert(red[i]);
	cerr << sources.size() << endl;

	for (int i = 0; i < k; i++) {
		set <int> alice = fill_followers(sources, A), not_alice;
		for (int j = 0; j < n; j++) 
			if (alice.count(j) == 0)
				not_alice.insert(j);

		//cerr << "iteration " << i << endl;
		//for (auto x : alice) cerr << x << ' '; cerr << endl;
		//for (auto x : not_alice) cerr << x << ' '; cerr << endl;

		set <int> bob = fill_followers(not_alice, B);
		//for (auto x : bob) cerr << x << ' '; cerr << endl;
		for (auto x : bob) sources.erase(x);
	}
	vector <int> winner(n);
	set <int> alice = fill_followers(sources, A);
	for (int i = 0; i < n; i++) winner[i] = B;
	for (auto x : alice) winner[x] = A;
	return winner;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 3404 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2280 KB Output is correct
2 Correct 0 ms 2280 KB Output is correct
3 Correct 0 ms 2280 KB Output is correct
4 Correct 0 ms 2280 KB Output is correct
5 Correct 0 ms 2280 KB Output is correct
6 Correct 0 ms 2280 KB Output is correct
7 Correct 0 ms 2280 KB Output is correct
8 Correct 0 ms 2280 KB Output is correct
9 Correct 0 ms 2280 KB Output is correct
10 Correct 0 ms 2280 KB Output is correct
11 Correct 0 ms 2280 KB Output is correct
12 Correct 0 ms 2280 KB Output is correct
13 Correct 0 ms 2280 KB Output is correct
14 Correct 0 ms 2280 KB Output is correct
15 Correct 0 ms 2280 KB Output is correct
16 Correct 0 ms 2280 KB Output is correct
17 Correct 0 ms 2280 KB Output is correct
18 Correct 0 ms 2280 KB Output is correct
19 Correct 0 ms 2280 KB Output is correct
20 Correct 0 ms 2280 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 3568 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 3684 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3552 KB Output is correct
2 Correct 16 ms 3420 KB Output is correct
3 Correct 19 ms 3420 KB Output is correct
4 Correct 9 ms 3260 KB Output is correct
5 Correct 0 ms 2412 KB Output is correct
6 Correct 3 ms 3476 KB Output is correct
7 Correct 6 ms 2832 KB Output is correct
8 Correct 3 ms 2856 KB Output is correct
9 Correct 6 ms 2848 KB Output is correct
10 Correct 0 ms 2420 KB Output is correct
11 Correct 6 ms 2884 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 3404 KB Execution timed out
2 Halted 0 ms 0 KB -