oj.uz

Submission #150238

# Submission time Handle Problem Language Result Execution time Memory
150238 2019-09-01T07:57:40 Z etyu(#3586, kimjihoon) Bulb Game (FXCUP4_bulb) C++17
0 / 100
 2 ms 380 KB 
#include "bulb.h"
#include <vector>
#include <iostream>
using namespace std;

int pl[300009], st[300009];
bool d[300009];
std::vector<int> l, r;

void dp(int n)
{
	if (pl[n] != 0) return;
	st[n] = 1;
	if (l[n] < 0) pl[n] = l[n];
	else {
		dp(l[n]);
		pl[n] = pl[l[n]];
		st[n] += st[l[n]];
	}
	if (r[n] >= 0) {
		dp(r[n]);
		st[n] += st[r[n]];
	}
	if ((l[n] >= 0 && d[l[n]]) || (r[n] == -2 || (r[n] >= 0 && pl[r[n]] == -2))) d[n] = false;
	else d[n] = true;
}

int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	int N = L.size();
	l = L; r = R;
	int rt = 0;
	for (int i = 0; i < N; i++) 
		if (pl[i] == 0) {
			dp(i);
			rt = i;
		}
	int hn = rt;
	while (hn >= 0)
		hn = l[hn];
	if (hn == -2) return 0;
	hn = rt;
	int sp = 0;
	while (hn >= 0) {
		int ts = sp;
		if (l[hn] >= 0) ts += st[l[hn]];
		bool f = true;
		if (ts != 0 && (r[hn] == -2 || (r[hn] >= 0 && pl[r[hn]] == -2))) f = false;
		if (r[hn] >= 0 && !d[r[hn]]) f = false;
		if (f) return 1;
		if (r[hn] == -2 || (r[hn] >= 0 && pl[r[hn]] == -2)) return 0;
		if (r[hn] >= 0) sp += st[r[hn]];
		hn = l[hn];
	}
	return (sp != 0);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Incorrect 2 ms 376 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Incorrect 2 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Incorrect 2 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -