oj.uz

Submission #975706

# Submission time Handle Problem Language Result Execution time Memory
975706 2024-05-05T18:46:39 Z ShaShi Game (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -