oj.uz

Submission #598552

# Submission time Handle Problem Language Result Execution time Memory
598552 2022-07-18T13:45:07 Z Lucpp Toy Train (IOI17_train) C++17
34 / 100
 254 ms 1552 KB 
#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[U[i]].push_back(V[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);
	}
	g.clear();
	g.resize(n);
	for(int i = 0; i < (int)U.size(); i++) g[V[i]].push_back(U[i]);
	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 7 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 1 ms 300 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 111 ms 1552 KB Output is correct
2 Correct 170 ms 1468 KB Output is correct
3 Correct 233 ms 1352 KB Output is correct
4 Correct 8 ms 1364 KB Output is correct
5 Correct 8 ms 1468 KB Output is correct
6 Correct 9 ms 1328 KB Output is correct
7 Correct 9 ms 1320 KB Output is correct
8 Correct 11 ms 1336 KB Output is correct
9 Correct 7 ms 1236 KB Output is correct
10 Correct 8 ms 1204 KB Output is correct
11 Correct 8 ms 1236 KB Output is correct
12 Correct 7 ms 1212 KB Output is correct
13 Correct 9 ms 1492 KB Output is correct
14 Correct 8 ms 1468 KB Output is correct
15 Correct 9 ms 1552 KB Output is correct
16 Correct 8 ms 1492 KB Output is correct
17 Correct 8 ms 1492 KB Output is correct
18 Correct 254 ms 1016 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1236 KB Output is correct
2 Correct 8 ms 1236 KB Output is correct
3 Correct 11 ms 1364 KB Output is correct
4 Correct 9 ms 1240 KB Output is correct
5 Correct 7 ms 1332 KB Output is correct
6 Correct 8 ms 1324 KB Output is correct
7 Correct 7 ms 1236 KB Output is correct
8 Correct 8 ms 1316 KB Output is correct
9 Correct 7 ms 1236 KB Output is correct
10 Correct 8 ms 1236 KB Output is correct
11 Correct 8 ms 1236 KB Output is correct
12 Correct 8 ms 1244 KB Output is correct
13 Correct 8 ms 1344 KB Output is correct
14 Correct 8 ms 1336 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1332 KB Output is correct
2 Correct 13 ms 1436 KB Output is correct
3 Correct 10 ms 1332 KB Output is correct
4 Correct 7 ms 1224 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 5 ms 852 KB Output is correct
8 Correct 5 ms 852 KB Output is correct
9 Correct 5 ms 816 KB Output is correct
10 Correct 2 ms 444 KB Output is correct
11 Correct 5 ms 852 KB Output is correct

Subtask #6
0 / 51.0

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