oj.uz

Submission #588265

# Submission time Handle Problem Language Result Execution time Memory
588265 2022-07-03T00:15:08 Z SAAD Game (APIO22_game) C++17
0 / 100
 1 ms 1744 KB 
#define F first
#define S second
#define rep(i,a,b) for(int i=a;!(a==b&&i!=b)&&((i<=b&&b>=a)||(i>=b&&a>=b));i+=(a<=b?1:-1))
#define pb push_back
#define Fbitl __builtin_ffs
#define bit1 __builtin_popcount
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
map <int, bool> mp;
#include "game.h"
const int N = 1e5/2;
vi x[N];
int mx[N], mn[N]; 
int n,k;
void init(int n, int k) {
	::n = n;
	::k = k;
	memset(mx, -1, sizeof(mx));
	for (auto& i : mn) {
		i = 100000;
	}
	for (int i = 0; i < k - 1; i++) {
		x[i].push_back(i + 1);
		mx[i] = i;
	}
	mx[k - 1] = k - 1;
}

int add_teleporter(int u, int v) {
	if (u < k && v < k) return 1;
	x[u].push_back(v);
	if (mx[u] >= mx[v] && v < k) {
		return 1;
	}
	if (mx[u] > mx[v]) {
		queue < int > q;
		q.push(u);
		while (!q.empty()) {
			int a = q.front();
			q.pop();
			for (auto i : x[a]) {
				if (mx[i] < mx[a]) {
					if (mx[a] >= mx[i] && i < k) {
						return 1;
					}
					q.push(i);
					mx[i] = mx[a];
				}
			}
		}
	}
	return 0;
}

Subtask #1
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1744 KB Output is correct
2 Incorrect 1 ms 1744 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1744 KB Output is correct
2 Incorrect 1 ms 1744 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1744 KB Output is correct
2 Incorrect 1 ms 1744 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1744 KB Output is correct
2 Incorrect 1 ms 1744 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1744 KB Output is correct
2 Incorrect 1 ms 1744 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -