Submission #593415

#	Time	Username	Problem	Language	Result	Execution time	Memory
593415		SAAD	Game (APIO22_game)	C++17	60 / 100	532 ms	3500 KiB

game

#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 >= v && 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[a] >= mx[i] && i < k) {
						return 1;
					}
				if (mx[i] < mx[a]) {
					
					q.push(i);
					mx[i] = mx[a];
				}
			}
		}
	}
	return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 0 / 40