Submission #631946

#	Time	Username	Problem	Language	Result	Execution time	Memory
631946		S2speed	Jail (JOI22_jail)	C++17	77 / 100	5113 ms	686824 KiB

jail

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
typedef long long ll;
typedef pair<ll , ll> pll;

const ll maxn = 2e5 + 17 , inf = 2e16;

vector<ll> adj[maxn];
ll jad[maxn][20] , bt[maxn] , ft[maxn] , tme , dis[maxn] , dep = 0;

void jDFS(ll r , ll par){
	bt[r] = tme++;
	dis[r] = dep++;
	jad[r][0] = par;
	for(ll j = 1 ; j < 20 ; j++){
		if(jad[r][j - 1] == -1) break;
		jad[r][j] = jad[jad[r][j - 1]][j - 1];
	}
	for(auto i : adj[r]){
		if(i == par) continue;
		jDFS(i , r);
	}
	ft[r] = tme;
	dep--;
	return;
}

ll find_jad(ll v , ll d){
	d = dis[v] - d;
	for(ll j = 19 ; ~j ; j--){
		if(d & (1 << j)){
			v = jad[v][j];
		}
	}
	return v;
}

bool too_masir(ll v , ll u , ll k){
	bool zv = (bt[v] >= bt[k] && ft[v] <= ft[k]) , zu = (bt[u] >= bt[k] && ft[u] <= ft[k]);
	if(!zv && !zu) return false;
	if(zv ^ zu) return true;
	ll hv = find_jad(v , dis[k] + 1) , hu = find_jad(u , dis[k] + 1);
	return (hv != hu);
}

ll n , m;
ll a[maxn] , b[maxn] , d[maxn] , x[maxn] , y[maxn];
vector<ll> jda[maxn];
priority_queue<pll , vector<pll> , greater<pll>> pq;
vector<pll> s1;

bool sub1(){
	s1.clear();
	for(ll i = 0 ; i < m ; i++){
		s1.push_back({a[i] , b[i]});
	}
	sort(all(s1));
	for(ll i = 1 ; i < m ; i++){
		if(s1[i].second < s1[i - 1].second) return false;
	}
	return true;
}

bool sub6(){
	for(ll i = 0 ; i < m ; i++){
		int v = a[i];
		while(true){
			if(x[v] != -1 && x[v] != i){
				jda[i].push_back(x[v]); d[x[v]]++;
			}
			if(y[v] != -1 && y[v] != i){
				jda[y[v]].push_back(i); d[i]++;
			}
			if(bt[b[i]] >= bt[v] && ft[b[i]] <= ft[v]) break;
			v = jad[v][0];
		}
		v = b[i];
		while(!(bt[a[i]] >= bt[v] && ft[a[i]] <= ft[v])){
			if(x[v] != -1 && x[v] != i){
				jda[i].push_back(x[v]); d[x[v]]++;
			}
			if(y[v] != -1 && y[v] != i){
				jda[y[v]].push_back(i); d[i]++;
			}
			v = jad[v][0];
		}
	}
	for(ll i = 0 ; i < m ; i++){
		pq.push({d[i] , i});
	}
	while(!pq.empty()){
		pll p = pq.top(); pq.pop();
		ll v = p.second;
		if(d[v] != p.first) continue;
		if(d[v] != 0){
			return false;
		}
		for(auto i : jda[v]){
			d[i]--;
			pq.push({d[i] , i});
		}
	}
	return true;
}

void solve(){
	while(!pq.empty()) pq.pop();
	tme = 0;
	cin>>n;
	for(ll i = 0 ; i < n ; i++){
		adj[i].clear(); jda[i].clear(); d[i] = 0; x[i] = y[i] = -1;
		for(ll j = 0 ; j < 20 ; j++) jad[i][j] = -1;
	}
	bool c = true;
	for(ll i = 1 ; i < n ; i++){
		ll v , u;
		cin>>v>>u; v--; u--;
		adj[v].push_back(u); adj[u].push_back(v);
		c &= (v == i - 1 && u == i);
	}
	jDFS(0 , -1);
	cin>>m;
	for(ll i = 0 ; i < m ; i++){
		cin>>a[i]>>b[i]; a[i]--; b[i]--;
		x[a[i]] = i; y[b[i]] = i;
	}
	if(c){
		cout<<(sub1() ? "Yes\n" : "No\n");
		return;
	}
	if(m > 500){
		cout<<(sub6() ? "Yes\n" : "No\n");
		return;
	}
	for(ll i = 0 ; i < m ; i++){
		for(ll j = 0 ; j < m ; j++){
			if(j == i) continue;
			if(too_masir(a[i] , b[i] , a[j])){
				jda[i].push_back(j); d[j]++;
			}
			if(too_masir(a[i] , b[i] , b[j])){
				jda[j].push_back(i); d[i]++;
			}
		}
	}
	for(ll i = 0 ; i < m ; i++){
		pq.push({d[i] , i});
	}
	while(!pq.empty()){
		pll p = pq.top(); pq.pop();
		ll v = p.second;
		if(d[v] != p.first) continue;
		if(d[v] != 0){
			cout<<"No\n";
			return;
		}
		for(auto i : jda[v]){
			d[i]--;
			pq.push({d[i] , i});
		}
	}
	cout<<"Yes\n";
	return;
}

int main(){
	ios_base::sync_with_stdio(false); 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: 0 / 23