Submission #587525

#	Time	Username	Problem	Language	Result	Execution time	Memory
587525		czhang2718	Jail (JOI22_jail)	C++17	100 / 100	1832 ms	341104 KiB

jail

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

#define rep(i,a,b) for(int i=a; i<=b; i++)
#define f first
#define s second
#define pb push_back
#define nl '\n'
typedef vector<int> vi;
typedef pair<int, int> pii;

const int N=120001;
const int K=17;
const int BN=4800001;
int t, n, m;
bool cyc;
vi adj[N];
vi adj2[BN];
bool seen[BN], vis[BN];
int par[N][K];
int he[N];
int id_start[N][K];
int id_end[N][K];
int st[N], nd[N];
int ti;

void dfs(int x, int p){
	id_start[x][0]=st[x];
	id_end[x][0]=nd[x];
	rep(i,1,K-1){
		par[x][i]=par[par[x][i-1]][i-1];
		id_start[x][i]=++ti;
		id_end[x][i]=++ti;
		if(id_start[x][i-1]) adj2[id_start[x][i-1]].pb(id_start[x][i]);
		if(id_start[par[x][i-1]][i-1]) adj2[id_start[par[x][i-1]][i-1]].pb(id_start[x][i]);

		if(id_end[x][i-1]) adj2[id_end[x][i]].pb(id_end[x][i-1]);
		if(id_end[par[x][i-1]][i-1]) adj2[id_end[x][i]].pb(id_end[par[x][i-1]][i-1]);
	}

	for(int k:adj[x]){
		if(k==p) continue;
		he[k]=he[x]+1;
		par[k][0]=x;
		dfs(k, x);
	}
}

int lca(int u, int v){
	if(he[u]<he[v]) swap(u,v);
	int d=he[u]-he[v];
	for(int i=0; i<K; i++){
		if(d&(1<<i)) u=par[u][i];
	}
	if(u==v) return u;
	for(int i=K-1; i>=0; i--){
		if(par[u][i] && par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i];
	}
	return par[u][0];
}

int dist(int u, int v){ return he[u]+he[v]-2*he[lca(u,v)]; }

void dfs2(int x){
	vis[x]=1;
	seen[x]=1;
	for(int k:adj2[x]){
		if(seen[k]){
			cyc=1; return;
		}
		if(vis[k]) continue;
		dfs2(k);
	}
	seen[x]=0;
}

void add_start(int a, int up, int to){
	int d=he[a]-he[up]+1;
	for(int i=K-1; i>=0; i--){
		if(d&(1<<i)){
			if(id_start[a][i]) adj2[id_start[a][i]].push_back(to);
			a=par[a][i];
		}
	}
}

void add_end(int a, int up, int to){
	// cout << "add end " << a << " - " << up << " TO " << to << nl;
	int d=he[a]-he[up]+1;
	for(int i=K-1; i>=0; i--){
		if(d&(1<<i)){
			if(id_end[a][i]) adj2[to].push_back(id_end[a][i]);
			a=par[a][i];
		}
	}
}

int binlift(int x, int d){
	int old=x;
	rep(i,0,K-1){
		if(d&(1<<i)) x=par[x][i];
	}
	return x;
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> t;
  while(t--){
  	cin >> n;
  	rep(i,1,n) adj[i].clear();
  	rep(i,1,n-1){
  		int u,v; cin >> u >> v;
  		adj[u].pb(v); adj[v].pb(u);
  	}
  	
  	cin >> m;
  	vector<pii> qu;
  	rep(i,1,m){
  		int s, e; cin >> s >> e;
  		qu.pb({s, e});
  		st[s]=i;
  		nd[e]=i;
  	}
  	ti=m;
  	dfs(1, 0);

  	// add edges
  	rep(i,1,m){
  		int a=qu[i-1].f, b=qu[i-1].s;
  		int lc=lca(a,b);
  		if(a==lc) add_start(b, binlift(b, he[b]-he[a]-1), i);
  		else add_start(par[a][0],lc, i), add_start(b,lc, i);
  		
  		if(b==lc) add_end(a, binlift(a, he[a]-he[b]-1), i);
  		else add_end(par[b][0],lc, i), add_end(a,lc, i);
  	}

  	cyc=0;
  	rep(i,1,ti){
  		if(cyc) break;
  		if(vis[i]) continue;
  		dfs2(i);
  	}

  	cout << (cyc?"No":"Yes") << nl;

  	rep(i,1,ti){
  		vis[i]=seen[i]=0;
  		adj2[i].clear();
  	}
  	rep(i,1,m){
  		int s=qu[i-1].f, e=qu[i-1].s;
  		st[s]=0;
  		nd[e]=0;
  	}
  }
}
// 

Compilation message (stderr)

jail.cpp: In function 'int binlift(int, int)':
jail.cpp:99:6: warning: unused variable 'old' [-Wunused-variable]
   99 |  int old=x;
      |      ^~~

• 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