Submission #1125045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125045		vako_p	Jail (JOI22_jail)	C++20	100 / 100	1461 ms	224308 KiB

jail

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
 
const int mxN = 1e6 + 5;
ll n,m,tt,in[mxN],out[mxN],p[mxN][21],st[mxN],ed[mxN],vis[mxN],pre[mxN],last[2][mxN],dis[mxN],heavy[mxN],head[mxN],bgn[2][mxN],pos[2][mxN];
vector<ll> v[mxN],vv[mxN],start[mxN],nds[mxN],comp[2];

void clear(){
	ll sz = 1;
	while(sz < m) sz *= 2;
	for(int i = 0; i <= 3 * sz; i++){
		vv[i].clear();
		vis[i] = 0;
	}
	for(int i = 0; i <= n; i++){
		v[i].clear();
		start[i].clear();
		heavy[i] = 0;
		head[i] = 0;
		nds[i].clear();
	}
	comp[0].clear();
	comp[1].clear();
	tt = 0;
}

void add(ll at, ll it, ll op){
	if(op){
		vv[at].pb(it);
//		cout << at << "--->" << it << '\n';
	} 
	else {
//	cout << it << "--->" << at << '\n';
	vv[it].pb(at);
	}
}

void dfs(ll at, ll par){
	in[at] = ++tt;
	p[at][0] = par;
//	for(int i = 1; i < 20; i++) p[at][i] = p[p[at][i - 1]][i - 1];
	ll mx = 0;
	pre[at] = 1;
	heavy[at] = 0;
	for(auto it : v[at]){
		if(it == par) continue;
		dis[it] = dis[at] + 1;
		dfs(it, at);
 		pre[at] += pre[it];
		if(pre[it] > mx){
			mx = pre[it];
			heavy[at] = it;
		}	
	}
 	out[at] = tt;
}

bool check(ll at, ll it){
	return (in[at] <= in[it] and out[at] >= out[it]);
}

struct segtree{
	vector<ll> vvv;
	ll sz = 1,op;
	
	void init(ll op1){
		op = op1;
		while(sz < mxN) sz *= 2;
		vvv.assign(sz, 0LL);
	}	
	
	void clear(ll sz1){
		sz = 1;
		while(sz < m) sz *= 2;
		for(int i = 0; i < 2 * sz - 1; i++){
			if(i < sz - 1) vvv[i] = sz1 + i;
			else vvv[i] = comp[op][i - sz + 1]; 
		}
		for(int i = 0; i < sz - 1; i++){
			add(vvv[i], vvv[2 * i + 1], op);
			add(vvv[i], vvv[2 * i + 2], op);
		}
	}
	
	void set(ll i, ll l, ll r, ll x, ll lx, ll rx){
		if(lx >= r or rx <= l) return;
		if(lx >= l and rx <= r){
			add(i, vvv[x], op);
			return;
		}
		ll mid = lx + (rx - lx) / 2;
		set(i, l, r, 2 * x + 1, lx, mid);
		set(i, l, r, 2 * x + 2, mid, rx);
	}
	
	void set(ll i, ll l, ll r){
//		cout << op <<  " set: " << i << ' ' << l << ' ' << r << "--> ";
//		for(int i = l; i < r; i++) cout << comp[op][i] << ' ';
//		cout << '\n';
		set(i, l, r, 0, 0, sz);
	}
};

segtree s[2];

void decompose(ll at, ll h){
	head[at] = h;
	bgn[0][at] = comp[0].size();
	bgn[1][at] = comp[1].size();
	for(auto it : start[at]){
		pos[0][it] = comp[0].size();
		comp[0].pb(it);
	}	
	for(auto it : nds[at]){
		pos[1][it] = comp[1].size();
		comp[1].pb(it);
	}
	last[0][at] = comp[0].size();
	last[1][at] = comp[1].size();
	if(heavy[at]) decompose(heavy[at], h);
	for(auto it : v[at]){
		if(it == p[at][0] or it == heavy[at]) continue;
		decompose(it, it);
	}
}

void add_edges(){
	decompose(1, 1);
	ll sz = 1;
	while(sz < m) sz *= 2;
	for(int i = 0; i < sz - m; i++){
		comp[0].pb(0);
		comp[1].pb(0);
	}
	s[0].clear(m + 1);
	s[1].clear(m + sz);
//	cout << "0 ------------- ";
//	for(auto it : comp[0]) cout << it << ' '; cout << '\n';
//	cout << "1 ------------- ";
//	for(auto it : comp[1]) cout << it << ' '; cout << '\n';
	for(int i = 1; i <= m; i++){
		ll at = st[i], it = ed[i];
		for(; head[at] != head[it]; at = p[head[at]][0]){
			if(dis[head[at]] < dis[head[it]]) swap(at, it);
//			cout << "--> " <<  it << ' ' << at << '\n';
			if(at == st[i]){
				s[0].set(i, bgn[0][head[at]], pos[0][i]);
				s[0].set(i, pos[0][i] + 1, last[0][at]);
				s[1].set(i, bgn[1][head[at]], last[1][at]); 
			}
			else if(at == ed[i]){
				s[1].set(i, bgn[1][head[at]], pos[1][i]);
				s[1].set(i, pos[1][i] + 1, last[1][at]); 
				s[0].set(i, bgn[0][head[at]], last[0][at]);
			}
			else{
				s[1].set(i, bgn[1][head[at]], last[1][at]);
				s[0].set(i, bgn[0][head[at]], last[0][at]); 
			}
		}
		if(dis[at] < dis[it]) swap(at, it);
//		cout << "---------------> " << at << ' ' << it << '\n';
		ll l0 = bgn[0][it],r0 = last[0][at],l1 = bgn[1][it],r1 = last[1][at];
		if(at == st[i]){
			r0 = pos[0][i];
			s[0].set(i, r0 + 1, last[0][at]);		  
		}
		else if(at == ed[i]){
			r1 = pos[1][i];
			s[1].set(i, r1 + 1, last[1][at]);
		}
		if(it == st[i]){
			l0 = pos[0][i];
			s[0].set(i, bgn[0][it], l0);
			l0++;		  
		}
		else if(it == ed[i]){
			l1 = pos[1][i];
			s[1].set(i, bgn[1][it], l1);
			l1++;
		}
		s[0].set(i, l0, r0);
		s[1].set(i, l1, r1);
	}
//	for(int i = 1; i <= 5 * sz; i++){
//		for(auto it : vv[i]) cout << i << ' ' << it << '\n';
//	}
} 


bool dfs1(ll at){
	if(vis[at]) return true;
	vis[at] = 1;
	for(auto it : vv[at]){
		if(vis[it] == 1) return false;
		if(!vis[it]) if(!dfs1(it)) return false;
	}
	vis[at] = 2;
	return true;
}

bool cycle(){
	for(int i = 1; i <= m; i++){
		if(!dfs1(i)) return false;
	}
	return true;
}


inline void solve(){
	cin >> n;
	for(int i = 0; i < n - 1; i++){
		ll a,b;
		cin >> a >> b;
		v[a].pb(b);
		v[b].pb(a);
	}
	cin >> m;
	for(int i = 1; i <= m; i++){
		cin >> st[i] >> ed[i];
		start[st[i]].pb(i);
		nds[ed[i]].pb(i);
	}
//	v[0].pb(1);
	dfs(1, 1);
//	for(int i = 2; i != 1; i = p[i][0]) cout << i << ' ';
//	cout << '\n';
	add_edges();
//	for(auto it : nds[2]) cout << it << '\n'; 
	if(cycle()) cout << "Yes" << '\n';
	else cout << "No" << '\n';
	clear();
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	s[0].init(0);
	s[1].init(1);
	ll t;
	cin >> t;
	while(t--) solve();
}

• 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