Submission #816588

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
816588	2023-08-09T05:48:02 Z	이종영(#10379)	Game (APIO22_game)	C++17	0 / 100	6 ms	14312 KB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N=3e5+5,H=22;
int n,k;
bool chk[N][H][2];
vector<int> g[N],gr[N];
void build(int h,int l,int r){
	if(l>r) return;
	int m=(l+r)>>1;
	for(int i=l;i<=m;i++) chk[i][h][0]=1;
	for(int i=m;i<=r;i++) chk[i][h][1]=1;
	if(l==r) return;
	build(h+1,l,m-1); build(h+1,m+1,r);
}
void init(int n_, int k_){
	n=n_;
	k=k_;
	for(int i=1;i<k;i++){
		g[i].emplace_back(i+1);
		gr[i+1].emplace_back(i);
	}
	build(1,1,k);
}
bool dfs(int u,int h){
	chk[u][h][1]=1;
	if(chk[u][h][0]) return 1;
	for(int v: g[u]) if(!chk[v][h][1]){
		if(dfs(v,h)) return 1;
	}
	return 0;
}
bool dfsr(int u,int h){
	chk[u][h][0]=1;
	if(chk[u][h][1]) return 1;
	for(int v: gr[u]) if(!chk[v][h][0]){
		if(dfsr(v,h)) return 1;
	}
	return 0;
}
bool add(int h,int l,int r,int u,int v){
	if(l>r) return 0;
	int m=(l+r)>>1;
	if(l==r) return 0;
	if(!chk[u][h][0]&&chk[v][h][0]){
		if(dfsr(u,h)) return 1;
	}
	if(chk[u][h][1]&&!chk[v][h][1]){
		if(dfs(v,h)) return 1;
	}
	if(chk[u][h][0]) return add(h+1,l,m-1,u,v);
	if(chk[u][h][1]) return add(h+1,m+1,r,u,v);
	return 0;
}
int add_teleporter(int u, int v){
	u++; v++;
	if(u==v&&u<=k) return 1;
	if(add(1,1,k,u,v)) return 1;
	g[u].emplace_back(v);
	gr[v].emplace_back(u);
	return 0;
}

Subtask #1

0.0 / 2.0

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

Subtask #2

0.0 / 10.0

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

Subtask #3

0.0 / 18.0

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

Subtask #4

0.0 / 30.0

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

Subtask #5

0.0 / 40.0

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