oj.uz

Submission #148658

# Submission time Handle Problem Language Result Execution time Memory
148658 2019-09-01T04:52:48 Z 서울대학교 연구공원 944동 삼성전자서울대연구소(#3600, ho94949, dotorya, zigui) Bulb Game (FXCUP4_bulb) C++17
0 / 100
 2 ms 376 KB 
#include "bulb.h"

#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

int son[300050][2];

int dp[300050][3];
int sz[300050];
void DFS(int n) {
	if (n == 300001 || n == 300002) {
		dp[n][0] = n - 300001;
		dp[n][1] = dp[n][2] = 0;
		sz[n] = 0;
		return;
	}

	DFS(son[n][0]);
	DFS(son[n][1]);
	int L = son[n][0], R = son[n][1];
	sz[n] = 1;
	sz[n] += sz[L] + sz[R];

	dp[n][0] = dp[L][0];
	dp[n][1] = dp[L][1];
	dp[n][2] = dp[L][2];

	if (dp[R][0] == 0) dp[n][1] = 1;
	else dp[n][2] = 1;
}

int FindWinner(int T, std::vector<int> L, std::vector<int> R){
	int N = L.size();
	for (int i = 0; i < N; i++) {
		if (L[i] == -1) L[i] = 300001;
		if (L[i] == -2) L[i] = 300002;
		if (R[i] == -1) R[i] = 300001;
		if (R[i] == -2) R[i] = 300002;
		son[i][0] = L[i], son[i][1] = R[i];
	}

	DFS(0);
	if (dp[0][0] == 1) return 0;

	int n = 0;
	for (int i = 1;; i++) {
		int L = son[n][0], R = son[n][1];
		
		if (dp[R][0] == 1) {
			if (i + sz[R] == N && !dp[R][2]) return 1;
			break;
		}
		if (!dp[R][2]) return 1;

		n = L;
		if (n >= 300001) break;
	}

	int c = 0;
	for (int n = 0; n <= 300000; n = son[n][0]) {
		int R = son[n][1];
		if (dp[R][0] == 1) c++;
	}
	if (c >= 2) return 0;
	if (c == 1) {
		for (int n = 0; n <= 300000; n = son[n][0]) {
			int R = son[n][1];
			if (dp[R][0] != 1) continue;
			if (dp[R][1]) return 1;
			return 0;
		}
	}
	for (int n = 0; n <= 300000; n = son[n][0]) {
		int R = son[n][1];
		if (dp[R][1]) return 1;
	}
	return 0;
}

Compilation message

bulb.cpp:25:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)  
 
bulb.cpp:26:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:336777216")

Subtask #1
0 / 11.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -