oj.uz

Submission #149425

# Submission time Handle Problem Language Result Execution time Memory
149425 2019-09-01T06:27:39 Z CHT를 사랑하는 모임(#3587, moonrabbit2, Retro3014, gs18115) Bulb Game (FXCUP4_bulb) C++17
11 / 100
 2 ms 420 KB 
#include "bulb.h"
#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 300010;

int l[MAX_N+1], r[MAX_N+1];
int N, T;
int l2[MAX_N+1];
int r2[MAX_N+1];
bool dp1[MAX_N+1];
bool dp2[MAX_N+1];

int num = 0;

void dfs(int x){
	if(r[x]>=0){
		dfs(r[x]);
		r2[x] = l2[r[x]];
	}else{
		r2[x] = -r[x];
	}
	if(l[x]>=0){
		dfs(l[x]);
		l2[x] = l2[l[x]];
		dp1[x] = (dp1[l[x]] && (r2[x]==1)); 
		dp2[x] = (dp2[l[x]] || (r2[x]==1));
	}else{
		l2[x] = -l[x];
		dp1[x] = (r2[x]==1);
		dp2[x] = (r2[x]==1 || l2[x]==1);
	}
}

bool dfs2(int x){
	if(r[x]>=0){
		if(dp1[r[x]] && (r2[x]==1)){
			return true;
		}
	}else{
		if(r2[x]==1){
			return true;
		}
	}
	if(r2[x]==1 &&  l[x]>=0){
		return dfs2(l[x]);
	}
	return false;
}

int FindWinner(int t, vector<int> L, vector<int> R){
	N = R.size(); T = t;
	for(int i=0; i<N; i++){
		l[i] = L[i]; r[i] = R[i];
	}
	dfs(0);
	if(l2[0]==2){
		return 0;
	}
	int idx = 0;
	while(1){
		num++;
		if(L[idx]<0){
			break;
		}
		idx = L[idx];
	}
	idx = 0;
	bool tf = true;
	int cnt = 1;
	while(1){
		if(R[idx]<0){
			if(R[idx]!=-1){
				tf = false;
			}
		}else{
			if(r2[idx]!=1){
				if(dp2[r[idx]]){
					cnt--;
					if(cnt<0){
						tf = false;
					}
				}else{
					tf = false;
				}
			}
		}
		if(L[idx]<0){
			break;
		}
		idx = L[idx];
	}
	if(tf)	return true;
	if(dp1[0] && (num!=N)){
		return true;
	}
	bool b = dfs2(0);
	return b;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 420 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 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -