Submission #633784

#	Time	Username	Problem	Language	Result	Execution time	Memory
633784		S2speed	Jail (JOI22_jail)	C++17	100 / 100	4011 ms	806624 KiB

jail

#include<bits/stdc++.h>
 
using namespace std;
 
#pragma GCC optimize ("Ofast")
 
#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;
 
const ll maxn = 1.2e5 + 17 , maxv = 5e6 + 17 , md = 1e9 + 7 , inf = 2e16;
 
vector<ll> adj[maxv] , jda[maxv] , tdj[maxn] , f;
ll jad[maxn][20] , dis[maxn] , dep = 0 , lb[maxn][20][2] , o;
ll a[maxn] , b[maxn] , c[maxv] , k;
bitset<maxv> mark;
 
void lDFS(ll r , ll par){
	dis[r] = dep++;
	lb[r][0][0] = o++;
	lb[r][0][1] = o++;
	jad[r][0] = par;
	ll t = inf;
	for(ll j = 1 ; j < 20 ; j++){
		if(jad[r][j - 1] == -1){
			t = j;
			break;
		}
		jad[r][j] = jad[jad[r][j - 1]][j - 1];
		lb[r][j][0] = o;
		adj[o].push_back(lb[r][j - 1][0]); jda[lb[r][j - 1][0]].push_back(o);
		adj[o].push_back(lb[jad[r][j - 1]][j - 1][0]); jda[lb[jad[r][j - 1]][j - 1][0]].push_back(o);
		o++;
		lb[r][j][1] = o;
		adj[lb[r][j - 1][1]].push_back(o); jda[o].push_back(lb[r][j - 1][1]);
		adj[lb[jad[r][j - 1]][j - 1][1]].push_back(o); jda[o].push_back(lb[jad[r][j - 1]][j - 1][1]);
		o++;
	}
	for(ll j = t ; j < 20 ; j++){
		lb[r][j][0] = lb[r][t - 1][0];
		lb[r][j][1] = lb[r][t - 1][1];
	}
	for(auto i : tdj[r]){
		if(i == par) continue;
		lDFS(i , r);
	}
	dep--;
	return;
}
 
ll find_jad(ll v , ll d){
	d = dis[v] - d;
	for(ll j = 0 ; j < 20 ; j++){
		if(d & (1 << j)){
			v = jad[v][j];
		}
	}
	return v;
}
 
ll lca(ll v , ll u){
	if(dis[v] > dis[u]) swap(v , u);
	u = find_jad(u , dis[v]);
	if(v == u) return v;
	for(ll j = 19 ; ~j ; j--){
		if(jad[v][j] != jad[u][j]){
			v = jad[v][j];
			u = jad[u][j];
		}
	}
	return jad[v][0];
}
 
void fDFS(ll r){
	mark[r] = true;
	for(auto i : adj[r]){
		if(mark[i]) continue;
		fDFS(i);
	}
	f.push_back(r);
	return;
}
 
void cDFS(ll r){
	c[r] = k;
	for(auto i : jda[r]){
		if(c[i] != -1) continue;
		cDFS(i);
	}
	return;
}
 
void solve(){
	ll n , m;
	cin>>n;
	for(ll i = 0 ; i < 40 * n ; i++){
		adj[i].clear(); jda[i].clear();
	}
	for(ll i = 0 ; i < n ; i++){
		tdj[i].clear();
		for(ll j = 0 ; j < 20 ; j++) jad[i][j] = -1;
	}
	for(ll i = 1 ; i < n ; i++){
		ll v , u;
		cin>>v>>u; v--; u--;
		tdj[v].push_back(u); tdj[u].push_back(v);
	}
	cin>>m; o = m;
	for(ll i = 0 ; i < m ; i++){
		cin>>a[i]>>b[i]; a[i]--; b[i]--;
	}
	lDFS(0 , -1);
	for(ll i = 0 ; i < m ; i++){
		ll l = lca(a[i] , b[i]);
		ll v = a[i];
		for(ll j = 19 ; ~j ; j--){
			ll u = jad[v][j];
			if(u == -1) continue;
			if(dis[u] < dis[l]) continue;
			adj[i].push_back(lb[v][j][0]); jda[lb[v][j][0]].push_back(i);
			v = u;
		}
		v = jad[a[i]][0];
		for(ll j = 19 ; ~j && v != -1 ; j--){
			ll u = jad[v][j];
			if(u == -1) continue;
			if(dis[u] < dis[l]) continue;
			jda[i].push_back(lb[v][j][1]); adj[lb[v][j][1]].push_back(i);
			v = u;
		}
		v = b[i];
		for(ll j = 19 ; ~j ; j--){
			ll u = jad[v][j];
			if(u == -1) continue;
			if(dis[u] < dis[l]) continue;
			jda[i].push_back(lb[v][j][1]); adj[lb[v][j][1]].push_back(i);
			v = u;
		}
		v = jad[b[i]][0];
		for(ll j = 19 ; ~j && v != -1 ; j--){
			ll u = jad[v][j];
			if(u == -1) continue;
			if(dis[u] < dis[l]) continue;
			adj[i].push_back(lb[v][j][0]); jda[lb[v][j][0]].push_back(i);
			v = u;
		}
		if(l != a[i]){
			jda[i].push_back(lb[l][0][1]); adj[lb[l][0][1]].push_back(i);
		}
		if(l != b[i]){
			adj[i].push_back(lb[l][0][0]); jda[lb[l][0][0]].push_back(i);
		}
		v = lb[b[i]][0][0];
		adj[v].push_back(i); jda[i].push_back(v);
		v = lb[a[i]][0][1];
		jda[v].push_back(i); adj[i].push_back(v);
	}
	f.clear();
	for(ll i = 0 ; i < o ; i++){
		c[i] = -1;
		mark[i] = false;
	}
	k = 0;
	for(ll i = 0 ; i < o ; i++){
		if(mark[i]) continue;
		fDFS(i);
	}
	reverse(all(f));
	for(auto i : f){
		if(c[i] != -1) continue;
		cDFS(i);
		k++;
	}
	for(ll i = 0 ; i < m ; i++){
		if(!mark[c[i]]){
			cout<<"No\n";
			return;
		}
		mark[c[i]] = false;
	}
	cout<<"Yes\n";
	return;
}
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
	ll T;
	cin>>T;
	while(T--) solve();
	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