Submission #586227

#	Time	Username	Problem	Language	Result	Execution time	Memory
586227		jamezzz	Game (APIO22_game)	C++17	30 / 100	4059 ms	17708 KiB

game

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

#define pb push_back
#define maxn 300005

int n,k;
bool vis[maxn];
vector<int> AL[maxn],AL2[maxn];

int dfs(int u){
	vis[u]=true;
	int ans=min(u,k);
	for(int v:AL[u]){
		if(!vis[v]){
			ans=min(ans,dfs(v));
		}
	}
	return ans;
}

int dfs2(int u){
	vis[u]=true;
	int ans=-1;
	if(u<k)ans=u;
	for(int v:AL2[u]){
		if(!vis[v]){
			ans=max(ans,dfs2(v));
		}
	}
	return ans;
}

void init(int _n,int _k){
	n=_n;k=_k;
}

int add_teleporter(int u,int v){
	AL[u].pb(v);
	AL2[v].pb(u);
	
	for(int i=0;i<n;++i)vis[i]=false;
	int low=dfs(v);
	for(int i=0;i<n;++i)vis[i]=false;
	int high=dfs2(u);
	if(low<=high)return 1;
	return 0;
}

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