제출 #1159716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159716		catch_me_if_you_can	게임 (APIO22_game)	C++20	0 / 100	17 ms	42716 KiB

game

#include<bits/stdc++.h>
#include "game.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back


const int MX = 3e5+5;
const int LMX = 12e5+69;

vector<int> adj[2][MX];//0 is regular, 1 is reversed.

int K;

bool death;

set<int> God;

set<int> L[MX];
set<int> R[MX];

vector<int> collect;

void build(int id, int l, int r)
{
	if(l > r)
		return;
	int m = (l+r)/2;
	for(int i = l; i <= m; i++)
		L[id].insert(i);
	for(int i = m+1; i <= r; i++)
		R[id].insert(i);
	build(2*id, l, m);
	build(2*id+1, m+1, r);
	return;
}

int vis[MX];

void dfs(int s, int u, const set<int> &avoid, const set<int> &chop)
{
	if(avoid.find(u) != avoid.end())
		return;
	if(chop.find(u) == chop.end())
		return;
	vis[u] = 1;
	collect.pb(u);
	for(int v: adj[s][u])
	{
		if(vis[v]) continue;
		dfs(s, v, avoid, chop);
	}
	return;
}

void upd(int id, int l, int r, int u, int v, const set<int> &chop)
{
	if(death) return;
	bool uL = (L[id].find(u)==L[id].end())^1; bool vL = (L[id].find(v)==L[id].end())^1;
	bool uR = (R[id].find(u)==R[id].end())^1; bool vR = (R[id].find(v)==R[id].end())^1;	
	bool uX = (!uL) && (!uR); bool vX = (!vL) && (!vR);
	int m = (l+r)/2;
	if(uR && vL)
	{
		death = true;
		return;
	}
	//Check Left Recurse.
	if(vL)
	{
		collect.clear();
		dfs(1, u, L[id], chop);
		for(auto s: collect)
		{
			vis[s] = 0;
			L[id].insert(s);
		}
		upd(id, l, m, u, v, L[id]);
		return;
	}
	//Check Right Recurse
	if(uR)
	{
		collect.clear();
		dfs(0, v, R[id], chop);
		for(auto s: collect)
		{
			vis[s] = 0;
			R[id].insert(s);
		}
		upd(id, l, m, u, v, R[id]);
		return;
	}
	return;
}

void init(int n, int k)
{
	K = k; death = false;
	for(int i = 0; i < n; i++)
	{
		adj[0][i].clear();
		adj[1][i].clear();
		God.insert(i);
	}
	for(int i = 1; i < k; i++)
	{
		adj[0][i-1].pb(i);
		adj[1][i].pb(i-1);
	}
	build(1, 0, k-1);
	return;
}

int add_teleporter(int u, int v)
{
	if(death) return death;
	adj[0][u].pb(v);
	adj[1][v].pb(u);
	upd(1, 0, K-1, u, v, God);
	return death;
}

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