Submission #1186229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186229		catch_me_if_you_can	Jail (JOI22_jail)	C++20	100 / 100	1488 ms	534076 KiB

jail

#include<bits/stdc++.h>
#pragma optimize_for_space
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int LMX = 1e7;

vector<int> g_adj[LMX];

int lnk[LMX];

struct graph
{
	int N, M;
	int SUM;
	int STUFF;
	int TIMER;
	stack<int> st;
	void reset()
	{
		while(st.size())
			st.pop();
		SUM = 0;
		STUFF = 0;
		N = 0;
		return;
	}
	int create()
	{
		N++;
		if((N == (int)(1e7)))
		{
			cout << "NAW\n";
			exit(0);
		}
		g_adj[N].clear();
		lnk[N] = 0;
		return N;
	}
	void add(int i, int j)
	{
		g_adj[i].pb(j);
		return;
	}
	void dfs(int u)
	{
		//cout << "At u = " << u << endl;
		st.push(u);
		int r;
		r = lnk[u] = ++TIMER;
		for(int v: g_adj[u])
		{
			if(lnk[v] != 0)
			{
				if(lnk[v] > 0)
					lnk[u] = min(lnk[u], lnk[v]);
				continue;
			}
			dfs(v);
			if(lnk[v] > 0)
				lnk[u] = min(lnk[u], lnk[v]);
		}
		if(r == lnk[u])
		{
			SUM = 0;
			while(true)
			{
				int x = st.top();
				if(x <= M)
					SUM++;
				st.pop();
				lnk[x] = -lnk[x];
				if(x == u)
					break;
			}
			STUFF = max(STUFF, SUM);
		}
		return;
	}
	bool check_cycle()
	{
		TIMER = 0;
		for(int i = 1; i <= N; i++)
		{
			/*for(int j: g_adj[i])
				cout << i << " " << j << endl;*/
			if(lnk[i])
				continue;
			dfs(i);
		}
		return (STUFF==1);
	}
};

graph work;

const int LOGM = 17;
const int MX = 12e4+1;
const int INF = 1e6;

int pa[LOGM][MX];
int lab[2][LOGM][MX];
vector<int> adj[MX];
int tin[MX], tout[MX];

int TIMER;

void dfs(int u, int p)
{
	tin[u] = ++TIMER;
	pa[0][u] = p;
	for(int i = 1; i < LOGM; i++)
		pa[i][u] = pa[i-1][pa[i-1][u]];
	for(int v: adj[u])
	{
		if(v==p)
			continue;
		dfs(v, u);
	}
	tout[u] = TIMER;
	return;
}

int LCA(int u, int v)
{
	if(tin[u] > tin[v])
		swap(u, v);
	if(tout[u] >= tout[v])
		return u;
	for(int i = LOGM-1; i >= 0; i--)
	{
		if(tout[pa[i][u]] < tin[v])
			u = pa[i][u];
	}
	return pa[0][u];
}

int conjure(int t, int i, int u)
{
	if(lab[t][i][u] != 0)
		return lab[t][i][u];
	if((lab[t][i][u] == 0) && (i == 0))
		return lab[t][i][u] = -1;
	int x = conjure(t, i-1, u);
	int y = conjure(t, i-1, pa[i-1][u]);
	if((x == -1) && (y == -1))
		return lab[t][i][u] = -1;
	if((x == -1))
		return y;
	if((y == -1))
		return x;
	int z = work.create();
	if(t == 0)
		work.add(z, x);
	else
		work.add(x, z);
	if(t == 0)
		work.add(z, y);
	else
		work.add(y, z);
	return lab[t][i][u] = z;
}

void add_edge(int x, int t, int i, int u)
{
	if(lab[t][i][u] == 0)
	{
		int s = conjure(t, i, u);
		lab[t][i][u] = s;
	}
	if(lab[t][i][u] == -1)
		return;
	if(t == 0)
		work.add(x, lab[t][i][u]);
	else
		work.add(lab[t][i][u], x);
	return;
}

void upd_edge(int x, int u, int p)
{
	for(int i = LOGM-1; i >= 0; i--)
	{
		if(tin[pa[i][u]] > tin[p])
		{
			add_edge(x, 0, i, u);
			add_edge(x, 1, i, u);
			u = pa[i][u]; 
		}
	}
	add_edge(x, 0, 0, u);
	add_edge(x, 1, 0, u);
	return;
}

signed main()
{
	fast();
	int q; cin >> q;
	while(q--)
	{
		int n; cin >> n;
		for(int i = 1; i <= n; i++)
			adj[i].clear();
		for(int i = 0; i < LOGM; i++)
		{
			for(int j = 0; j <= n; j++)
			{
				for(int t = 0; t < 2; t++)
					pa[i][j] = lab[t][i][j] = 0;
			}
		}
		work.reset();
		int m = n-1;
		while(m--)
		{
			int u, v; cin >> u >> v;
			adj[u].pb(v); adj[v].pb(u);
		}
		vector<array<int, 3>> sp;
		cin >> m; work.M = m;
		while(m--)
		{
			int S, E; cin >> S >> E;
			int id = work.create();
			sp.pb({id, S, E});
			lab[0][0][S] = id;
			lab[1][0][E] = id;
		}
		TIMER = 0;
		tin[0] = -INF; tout[0] = INF;
		dfs(1, 0);
		for(auto [id, u, v]: sp)
		{
			//cout << id << " " << u << " " << v << endl;
			int w = LCA(u, v);
			//cout << w << endl;
			upd_edge(id, u, w);
			upd_edge(id, v, w);
			add_edge(id, 0, 0, w);
			add_edge(id, 1, 0, w);
		}
		if(work.check_cycle())
			cout << "Yes\n";
		else
			cout << "No\n";
	}
	return 0;
}	

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23