Submission #1161880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161880		catch_me_if_you_can	Game (APIO22_game)	C++20	12 / 100	4016 ms	43360 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

int Tc;

int NN, MM, KK;
vector<in> EDGES;

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)
{
	//cout << "Called!" << endl;
	int m = (l+r)/2;
	for(int i = l; i <= m; i++)
		L[id].insert(i);
	for(int i = m; i <= r; i++)
		R[id].insert(i);
	if(l==r)
		return;
	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;
	for(int v: adj[s][u])
	{
		collect.pb(v);
		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)
{
	//cout << "Updating " << l << " " << r << " for edge " << u << " " << v << endl;   
	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)
	{
		//cout << "There was a deadly cycle." << endl;
		death = true;
		return;
	}
	//Check Left Recurse.
	if(vL)
	{
		collect.clear();
		collect.pb(u);
		dfs(1, u, L[id], chop);
		for(auto s: collect)
		{
			vis[s] = 0;
			if(R[id].find(s) != R[id].end())
				death = true;
			L[id].insert(s);
		}
		//cout << "Left Recursing due to vertex v = " << v << " being in Left set " << endl;
		if(l == r)
			return;
		upd(2*id, l, m, u, v, L[id]);
		return;
	}
	//Check Right Recurse
	if(uR)
	{
		collect.clear();
		collect.pb(v);
		dfs(0, v, R[id], chop);
		for(auto s: collect)
		{
			vis[s] = 0;
			if(L[id].find(s) != L[id].end())
				death = true;
			R[id].insert(s);
		}
		//cout << "Right Recursing due to vertex u = " << u << " being in Right set " << endl;
		if(l == r)
			return;
		upd(2*id+1, m+1, r, u, v, R[id]);
		return;
	}
	if(uL && vR)
		return;
	if(uL)
		upd(2*id, l, m, u, v, L[id]);
	if(vR)
		upd(2*id+1, m+1, r, u, v, R[id]);
	return;
}

void init(int n, int k)
{
	K = k; death = false;
	God.clear();
	for(int i = 0; i < n; i++)
	{
		adj[0][i].clear();
		adj[1][i].clear();
		God.insert(i);
	}
	for(int i = 1; i <= (4*n+5); i++)
	{
		L[i].clear();
		R[i].clear();
	}
	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;
}

vector<int> ncollect;

int nvis[MX];

void explore(int u)
{
	ncollect.pb(u);
	for(int v: adj[0][u])
	{
		if(nvis[v]) continue;
		nvis[v] = 1;
		explore(v);
	}
	return;
}

bool check(int k)
{
	bool ok = false;
	for(int i = 0; i < k; i++)
	{
		explore(i);
		if(nvis[i] == 1)
			ok = true;
		for(auto k: ncollect)
			nvis[k] = 0;
		ncollect.clear();
	}
	return ok;
}

int add_teleporter(int u, int v)
{
	if(death) return death;
	if(u == v)
	{
		if(u < K)
			return death = true;
		else
			return death;
	}
	adj[0][u].pb(v);
	adj[1][v].pb(u);
	upd(1, 0, K-1, u, v, God);
	int okk = check(K);
	/*if(death != okk)
	{
		cout << "Problem observed in Test Case = " << Tc << endl;
		cout << "1\n";
		cout << NN << " " << MM << " " << KK << endl;
		for(auto [x, y]: EDGES)
			cout << x << " " << y << endl;
		cout << "Copium karo happaned with edge " << u << " " << v << endl;
		cout << "Expected " << okk  << " received " << death << endl;
	}*/
	//assert(death == okk);
	return death = okk;
}

/*signed main()
{
	int t; cin >> t;
	Tc = 1;
	while(t--)
	{
		int n, m, k;
		cin >> n >> m >> k;
		EDGES.clear();
		NN = n; MM = m; KK = k;
		init(n, k);
		vector<in> edge(m+1);
		int pp = m+1;
		for(int i = 1; i <= m; i++)
		{
			int x, y; cin >> x >> y;
			EDGES.pb({x, y});
			if(add_teleporter(x, y))
				pp = min(pp, i);
			edge[i] = {x, y};
		}
		Tc++;
	}
	return 0;
}*/

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