Submission #598614

#	Time	Username	Problem	Language	Result	Execution time	Memory
598614		Lucpp	장난감 기차 (IOI17_train)	C++17	100 / 100	1150 ms	1660 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> win;
vector<int> deg;
vector<bool> alive;

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);
	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;
		}
		auto tempG = g;
		auto tempDeg = deg;
		calcWin();
		g = tempG;
		deg = tempDeg;
		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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51