oj.uz

답안 #975706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975706 2024-05-05T18:46:39 Z ShaShi 게임 (APIO22_game) C++17
2 / 100
 14 ms 51800 KB 
#include "game.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define pii pair<int, int>



using namespace std;

typedef long long ll;


const int MAXN = (int)1e6 + 7;
const int LG = 60;


int dp[MAXN], pd[MAXN];
vector<int> adj[MAXN][2];
bool seen[MAXN];
int N, K, X;


bool check(int x) {
	if (dp[x] <= pd[x]) return 1;
	return 0;
}


void init(int n, int k) {
	N = n;
	K = k;

	for (int i=0; i<N; i++) dp[i] = pd[i] = -1;
}


void DFS(int v, bool b) {
	seen[v] = 1;

	if (b) dp[v] = (dp[v] == -1? X : min(dp[v], X));
	else pd[v] = (pd[v] == -1? X : max(pd[v], X));

	for (int u:adj[v][b]) if (!seen[u]) DFS(u, b);
}


int add_teleporter(int u, int v) {
	if (u < K && v < K) {
		if (u >= v) return 1;
		return 0;
	}

	adj[u][0].pb(v); adj[v][1].pb(u);

	fill(seen, seen+N+1, 0);

	if (u < K) {
		X = u;
		DFS(u, 0);
	} else if (v < K) {
		X = v;
		DFS(v, 1);
	} else {
		if (dp[v] != -1 && pd[u] != -1 && dp[v] <= pd[u]) return 1;
	}

	for (int i=K; i<N; i++) if (dp[i] != -1 && pd[i] != -1 && dp[i] <= pd[i]) return 1;


	return 0;
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 51544 KB Output is correct
2 Correct 11 ms 51544 KB Output is correct
3 Correct 11 ms 51544 KB Output is correct
4 Correct 11 ms 51616 KB Output is correct
5 Correct 13 ms 51800 KB Output is correct
6 Correct 13 ms 51544 KB Output is correct
7 Correct 14 ms 51544 KB Output is correct

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 51544 KB Output is correct
2 Correct 11 ms 51544 KB Output is correct
3 Correct 11 ms 51544 KB Output is correct
4 Correct 11 ms 51616 KB Output is correct
5 Correct 13 ms 51800 KB Output is correct
6 Correct 13 ms 51544 KB Output is correct
7 Correct 14 ms 51544 KB Output is correct
8 Correct 11 ms 51544 KB Output is correct
9 Correct 11 ms 51544 KB Output is correct
10 Correct 12 ms 51688 KB Output is correct
11 Correct 11 ms 51544 KB Output is correct
12 Incorrect 11 ms 51544 KB Wrong Answer[1]
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 51544 KB Output is correct
2 Correct 11 ms 51544 KB Output is correct
3 Correct 11 ms 51544 KB Output is correct
4 Correct 11 ms 51616 KB Output is correct
5 Correct 13 ms 51800 KB Output is correct
6 Correct 13 ms 51544 KB Output is correct
7 Correct 14 ms 51544 KB Output is correct
8 Correct 11 ms 51544 KB Output is correct
9 Correct 11 ms 51544 KB Output is correct
10 Correct 12 ms 51688 KB Output is correct
11 Correct 11 ms 51544 KB Output is correct
12 Incorrect 11 ms 51544 KB Wrong Answer[1]
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 51544 KB Output is correct
2 Correct 11 ms 51544 KB Output is correct
3 Correct 11 ms 51544 KB Output is correct
4 Correct 11 ms 51616 KB Output is correct
5 Correct 13 ms 51800 KB Output is correct
6 Correct 13 ms 51544 KB Output is correct
7 Correct 14 ms 51544 KB Output is correct
8 Correct 11 ms 51544 KB Output is correct
9 Correct 11 ms 51544 KB Output is correct
10 Correct 12 ms 51688 KB Output is correct
11 Correct 11 ms 51544 KB Output is correct
12 Incorrect 11 ms 51544 KB Wrong Answer[1]
13 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 51544 KB Output is correct
2 Correct 11 ms 51544 KB Output is correct
3 Correct 11 ms 51544 KB Output is correct
4 Correct 11 ms 51616 KB Output is correct
5 Correct 13 ms 51800 KB Output is correct
6 Correct 13 ms 51544 KB Output is correct
7 Correct 14 ms 51544 KB Output is correct
8 Correct 11 ms 51544 KB Output is correct
9 Correct 11 ms 51544 KB Output is correct
10 Correct 12 ms 51688 KB Output is correct
11 Correct 11 ms 51544 KB Output is correct
12 Incorrect 11 ms 51544 KB Wrong Answer[1]
13 Halted 0 ms 0 KB -