Submission #975361

#	Time	Username	Problem	Language	Result	Execution time	Memory
975361		happy_node	Jail (JOI22_jail)	C++17	100 / 100	1281 ms	323092 KiB

jail

#include <bits/stdc++.h>
using namespace std;

const int MX=1.2e5+5;
int Q,N,M;
int S[MX], T[MX];

vector<int> adj[MX], cyc[MX*40];

int up[MX][20], dep[MX], deg[MX*40];

int timer=0,tin[MX],tout[MX];

int valS[MX], valT[MX];

int idS[MX][20], idT[MX][20];

void dfs(int v, int p) {
	tin[v]=++timer;
	up[v][0]=p;
	for(int k=1;k<18;k++) {
		up[v][k]=up[up[v][k-1]][k-1];
	}
	for(auto u:adj[v]) {
		if(u==p) continue;
		dep[u]=dep[v]+1;
		dfs(u,v);
	}
	tout[v]=timer;
}

bool isAnc(int u, int v) { // u is the ancestor
	return tin[u]<=tin[v] && tout[v]<=tout[u];
}

int getLCA(int u, int v) {
	if(isAnc(u,v)) return u;
	if(isAnc(v,u)) return v;

	for(int k=17;k>=0;k--) {
		if(up[u][k]!=0 && !isAnc(up[u][k],v)) {
			u=up[u][k];
		}
	}
	return up[u][0];
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>Q;

	while(Q--) {
		cin>>N;

		for(int i=1;i<=N;i++) {
			valS[i]=-1;
			valT[i]=-1;
			dep[i]=0;
			adj[i].clear();

			for(int j=0;j<18;j++) {
				up[i][j]=0;
				idS[i][j]=0;
				idT[i][j]=0;
			}
		}

		for(int i=0;i<N-1;i++) {
			int u,v;
			cin>>u>>v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}

		tin[0]=0;
		tout[0]=1e9;

		timer=0;
		dfs(1,0);

		cin>>M;

		int id=M;
		for(int i=1;i<=N;i++) {
			for(int j=0;j<18;j++) {
				idS[i][j]=id++;
			}
		}
		for(int i=1;i<=N;i++) {
			for(int j=0;j<18;j++) {
				idT[i][j]=id++;
			}
		}
		for(int i=1;i<=N;i++) {
			for(int j=0;j<17;j++) {
				cyc[idS[i][j]].push_back(idS[i][j+1]);
				if(j>0 && up[i][j-1]!=0) cyc[idS[up[i][j-1]][j]].push_back(idS[i][j+1]);

				cyc[idT[i][j+1]].push_back(idT[i][j]);
				if(j>0 && up[i][j-1]!=0) cyc[idT[i][j+1]].push_back(idT[up[i][j-1]][j]);
			}
		}

		for(int i=0;i<M;i++) {
			cin>>S[i]>>T[i];

			valS[S[i]]=i;
			valT[T[i]]=i;
		}

		for(int i=0;i<M;i++) {
			int L=getLCA(S[i],T[i]);

			// everything within par(S[i]) to before L don't have tricky cases
			if(dep[S[i]]-dep[L]>=2) {
				int v=up[S[i]][0];
				for(int k=16;k>=0;k--) {
					if(up[v][k]!=0 && !isAnc(up[v][k],L)) {
						cyc[idS[v][k+1]].push_back(i);
						cyc[i].push_back(idT[v][k+1]);
						v=up[v][k];
					}
				}
				cyc[idS[v][0]].push_back(i);
				cyc[i].push_back(idT[v][0]);
			}
			if(dep[T[i]]-dep[L]>=2) {
				int v=up[T[i]][0];
				for(int k=16;k>=0;k--) {
					if(up[v][k]!=0 && !isAnc(up[v][k],L)) {
						cyc[idS[v][k+1]].push_back(i);
						cyc[i].push_back(idT[v][k+1]);
						v=up[v][k];
					}
				}
				cyc[idS[v][0]].push_back(i);
				cyc[i].push_back(idT[v][0]);
			}

			// connect to the base
			cyc[i].push_back(idS[S[i]][0]);
			cyc[idT[T[i]][0]].push_back(i);

			// this is for handling the cases on the edge to make sure 
			// we don't connect i with itself
			vector<int> cands={S[i],L,T[i]};
		
			for(auto x:cands) {
				// we just naively connect edges since there are <= 3 candidates
				if(valS[x]!=-1 && valS[x]!=i) 
					cyc[valS[x]].push_back(i);
				if(valT[x]!=-1 && valT[x]!=i) 
					cyc[i].push_back(valT[x]);
			}
		}

		for(int i=0;i<id;i++) {
			for(auto j:cyc[i]) {
				deg[j]+=1;
			}
		}

		queue<int> q;
		for(int i=0;i<id;i++) {
			if(!deg[i]) q.push(i);
		}

		int ans=0;
		while(!q.empty()) {
			auto v=q.front(); q.pop();
			ans+=1;
			for(auto u:cyc[v]) {
				deg[u]-=1;
				if(!deg[u]) q.push(u);
			}
		}

		cout<<(ans==id?"Yes":"No")<<'\n';

		for(int i=0;i<id;i++) {
			cyc[i].clear();
			deg[i]=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