제출 #598444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598444		Lucpp	장난감 기차 (IOI17_train)	C++17	11 / 100	262 ms	1560 KiB

train

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

int n;
vector<int> own;
vector<int> charge;
vector<vector<int>> g;
vector<int> state;
vector<int> win;
vector<int> deg;
vector<bool> alive;

bool dfs(int u){
	state[u] = 1;
	bool cycle = false;
	for(int v : g[u]){
		if(own[v] == 0 && charge[v] == 0){
			if(state[v] == 0){
				cycle |= dfs(v);
			}
			else if(state[v] == 1) cycle = true;
		}
	}
	state[u] = 2;
	if(cycle) win[u] = 0;
	return cycle;
}

void go(int u){
	for(int i = 0; i < (int)g[u].size(); i++){
		int v = g[u][i];
		if(win[v] != -1) continue;
		if(own[v] == win[u]){
			win[v] = win[u];
			go(v);
		}
		else{
			swap(g[u][i], g[u].back());
			g[u].pop_back();
			i--;
			if(--deg[v] == 0){
				win[v] = win[u];
				go(v);
			}
		}
	}
}

void calcWin(){
	for(int u = 0; u < n; u++){
		if(win[u] != -1) go(u);
	}
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> U, vector<int> V) {
	own = a;
	charge = r;
	n = (int)a.size();
	g.clear();
	g.resize(n);
	deg.assign(n, 0);
	for(int i = 0; i < (int)U.size(); i++){
		deg[U[i]]++;
		g[V[i]].push_back(U[i]);
	}
	win.assign(n, -1);
	state.assign(n, 0);
	for(int u = 0; u < n; u++){
		if(own[u] == 0 && charge[u] == 0 && state[u] == 0) dfs(u);
	}
	alive.assign(n, true);
	while(true){
		calcWin();
		for(int u = 0; u < n; u++){
			if(win[u] == 0) alive[u] = false;
		}
		win.assign(n, -1);
		for(int u = 0; u < n; u++){
			if(alive[u] && charge[u]) win[u] = 1;
		}
		calcWin();
		bool done = true;
		for(int u = 0; u < n; u++){
			if(alive[u]){
				if(win[u] == -1) done = false, win[u] = 0;
				if(win[u] == 1) win[u] = -1;
			}
		}
		if(done) break;
	}
	vector<int> w(n);
	for(int i = 0; i < n; i++) w[i] = alive[i];
	return w;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51