Submission #588555

#	Time	Username	Problem	Language	Result	Execution time	Memory
588555		jamezzz	Game (APIO22_game)	C++17	100 / 100	1591 ms	87676 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define maxn 300005

//earliest node i can reach is in [m+1,r]
//latest that can reach node i is in [l,m]
int n,k,l[maxn],r[maxn],ans;
vector<int> in[maxn],out[maxn];

void init(int _n,int _k){
	n=_n+1;k=_k+1;
	for(int i=0;i<k;++i)l[i]=i,r[i]=i+1;
	for(int i=k;i<n;++i)l[i]=0,r[i]=k;
}

void ppo(int u);

void fix(int u,int v){
	if(r[u]<=l[v])return;//earliest v can reach after latest that can reach u, impossible
	if(r[v]<=l[u]){//earliest that v can reach before latest that can reach u, possible
		ans=1;
		return;
	}
	if(l[u]==l[v]&&r[u]==r[v])return;
	int um=(l[u]+r[u])>>1,vm=(l[v]+r[v])>>1;
	if(r[v]<=um){//u can reach something earlier that is in bucket [l,m] so ppo down
		r[u]=um;
		ppo(u);
	}
	else if(vm<=l[u]){//something can reach v that is in bucket [m+1,r] so ppo down
		l[v]=vm;
		ppo(v);
	}
}

void ppo(int u){
	for(int v:out[u])fix(u,v);
	for(int v:in[u])fix(v,u);
}

int add_teleporter(int u,int v){
	++u,++v;
	if(v<k)--v;
	out[u].pb(v);
	in[v].pb(u);
	fix(u,v);
	return ans;
}

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