Submission #415675

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
415675	2021-06-01T11:02:55 Z	SeDunion	Toy Train (IOI17_train)	C++17	0 / 100	2000 ms	10952 KB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;

const int A = 1;
const int B = 0;

vector<int>g[(int)2e5+22], rg[(int)2e5+22];

int n, m;

int deg[(int)2e5+22];

queue<int>q;

vector<int>f(const int type, const vector<int>&S, const vector<int>&a, const vector<int>&answer) {
	for (int i = 0 ; i < n ; ++ i) {
		if (answer[i] != -1) {
			deg[i] = -1;
			continue;
		}
		deg[i] = 0;
		for (int j : g[i]) {
			deg[i] += answer[j] == -1;
		}
	}
	for (int i : S) {
		deg[i] = -1;
		q.push(i);
	}
	while (q.size()) {
		int v = q.front(); q.pop();
		for (int from : rg[v]) if (deg[from] != -1) {
			if (a[from] == type) {
				deg[from] = -1;
				q.push(from);
			} else {
				if (--deg[from] == 0) {
					deg[from] = -1;
					q.push(from);
				}
			}
		}
	}
	vector<int>ans;
	for (int i = 0 ; i < n ; ++ i) {
		if (deg[i] == -1) {
			ans.emplace_back(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]].emplace_back(v[i]);
		rg[v[i]].emplace_back(u[i]);
	}
	vector<int>answer(n, -1);
	vector<int>R;
	vector<int>fa;
	vector<int>nfa;
	vector<int>infa;
	vector<int>fb;
	while (true) {
		R.clear();
		for (int i = 0 ; i < n ; ++ i) {
			if (r[i] && answer[i] == -1) {
				R.emplace_back(i);
			}
		}
		if (R.empty()) {
			for (int i = 0 ; i < n ; ++ i) {
				if (answer[i] == -1) {
					answer[i] = 0;
				}
			}
			break;
		}
		fa = f(A, R, a, answer);
		infa.assign(n, 0);
		for (int i : fa) infa[i] = 1;
		nfa.clear();
		for (int i = 0 ; i < n ; ++ i) {
			if (answer[i] == -1 && infa[i] == 0) {
				nfa.emplace_back(i);
			}
		}
		fb = f(B, nfa, a, answer);
		if (fb.empty()) {
			for (int i = 0 ; i < n ; ++ i) {
				if (answer[i] == -1) {
					answer[i] = 1;
				}
			}
			break;
		}
		for (int i : fb) answer[i] = 0;
	}
	return answer;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2021 ms	10352 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2054 ms	9672 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	193 ms	10948 KB	Output is correct
2	Correct	377 ms	10952 KB	Output is correct
3	Correct	462 ms	10936 KB	Output is correct
4	Execution timed out	2058 ms	10864 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-