Submission #598444

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
598444	2022-07-18T11:24:43 Z	Lucpp	Toy Train (IOI17_train)	C++17	11 / 100	262 ms	1560 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	852 KB	3rd lines differ - on the 26th token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	3rd lines differ - on the 2nd token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	1560 KB	Output is correct
2	Correct	148 ms	1492 KB	Output is correct
3	Correct	223 ms	1336 KB	Output is correct
4	Correct	8 ms	1420 KB	Output is correct
5	Correct	7 ms	1372 KB	Output is correct
6	Correct	8 ms	1364 KB	Output is correct
7	Correct	8 ms	1336 KB	Output is correct
8	Correct	6 ms	1364 KB	Output is correct
9	Correct	5 ms	1236 KB	Output is correct
10	Correct	6 ms	1236 KB	Output is correct
11	Correct	6 ms	1308 KB	Output is correct
12	Correct	5 ms	1208 KB	Output is correct
13	Correct	6 ms	1504 KB	Output is correct
14	Correct	7 ms	1460 KB	Output is correct
15	Correct	6 ms	1468 KB	Output is correct
16	Correct	6 ms	1552 KB	Output is correct
17	Correct	6 ms	1460 KB	Output is correct
18	Correct	262 ms	1004 KB	Output is correct