Submission #586268

#	Time	Username	Problem	Language	Result	Execution time	Memory
586268		jamezzz	게임 (APIO22_game)	C++17	60 / 100	4064 ms	38376 KiB

game

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

#define pb push_back
#define maxn 300005

int n,k,low[maxn],high[maxn];
vector<int> AL[maxn],AL2[maxn];

void dfs(int u,int x){
	for(int v:AL[u]){
		if(high[v]<x){
			high[v]=x;
			dfs(v,x);
		}
	}
}

void dfs2(int u,int x){
	for(int v:AL2[u]){
		if(x<low[v]){
			low[v]=x;
			dfs2(v,x);
		}
	}
}

void init(int _n,int _k){
	n=_n;k=_k;
	for(int i=0;i<k;++i){
		low[i]=high[i]=i;
	}
	for(int i=k;i<n;++i){
		high[i]=-1;
		low[i]=k;
	}
	for(int i=0;i<k-1;++i){
		AL[i].pb(i+1);
		AL2[i+1].pb(i);
	}
}

int add_teleporter(int u,int v){
	
	if(v<=u&&u<k)return 1;
	AL[u].pb(v);
	AL2[v].pb(u);
	dfs(u,high[u]);
	dfs2(v,low[v]);
	
	/*
	printf("low: ");
	for(int i=0;i<n;++i)printf("%d ",low[i]);
	printf("\n");
	printf("high: ");
	for(int i=0;i<n;++i)printf("%d ",high[i]);
	printf("\n");
	*/
	
	if(u>=k&&low[u]<=high[u])return 1;
	if(v>=k&&low[v]<=high[v])return 1;
	return 0;
}

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