Submission #1185897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185897		catch_me_if_you_can	Jail (JOI22_jail)	C++20	72 / 100	1096 ms	1114112 KiB

jail

#include<bits/stdc++.h>
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)

struct graph
{
	vector<vector<int>> adj;
	vector<vector<int>> adj_rev;
	int N, M;
	vector<bool> vis;
	vector<int> order;
	int SUM;
	void reset()
	{
		adj.clear();
		adj_rev.clear();
		adj.pb({});
		adj_rev.pb({});
		vis.clear();
		order.clear();
		SUM = 0;
		N = 0;
		return;
	}
	int create()
	{
		adj.pb({});
		adj_rev.pb({});
		return ++N;
	}
	void add(int i, int j)
	{
		adj[i].pb(j);
		adj_rev[j].pb(i);
		return;
	}
	void dfs(int u)
	{
		//cout << "Running u = " << u << endl;
		if(vis[u])
			return;
		vis[u] = 1;
		for(int v: adj[u])
		{
			//cout << "Descending into v = " << v << endl;
			dfs(v);
		}
		order.pb(u);
		return;
	}
	void dfs_rev(int u)
	{
		//cout << u << endl;
		if(vis[u])
			return;
		vis[u] = 1;
		if(u <= M)
			SUM++;
		for(int v: adj_rev[u])
			dfs_rev(v);
		return;
	}
	bool check_cycle()
	{
		//cout << "N = " << N << "\n";
		vis.assign(N+1, false);
		for(int i = 1; i <= N; i++)
		{
			if(vis[i])
				continue;
			dfs(i);
		}
		reverse(order.begin(), order.end());
		vis.assign(N+1, false);
		for(int u: order)
		{
			//cout << "Curr = u = " << u << endl;
			if(vis[u])
				continue;
			SUM = 0;
			dfs_rev(u);
			if(SUM >= 2)
				return false;
		}
		return true;
	}
};

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

void add_edge(int x, int t, int i, int u)
{
	if(lab[t][i][u] == 0)
	{
		int s = conjure(t, i, u);
		if(s == -1)
			return; 
		lab[t][i][u] = s;
	}
	
	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: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23