제출 #415679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415679		SeDunion	장난감 기차 (IOI17_train)	C++17	100 / 100	799 ms	10904 KiB

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 && answer[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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51