Submission #709423

#	Time	Username	Problem	Language	Result	Execution time	Memory
709423		minhcool	Jail (JOI22_jail)	C++17	0 / 100	5103 ms	54832 KiB

jail

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
const int mod = 1e9 + 7, oo = 1e18 + 7;
 
int n, m;
 
vector<int> Adj[N];
vector<int> Adj2[N];// all nodes j that go after i
 
int deg[N];
 
int anc[N][20], d[N]; 

int le[N], ri[N];
 
void init(){
	for(int i = 1; i <= max(n, m); i++){
		Adj[i].clear();
		Adj2[i].clear();
		deg[i] = 0;
		for(int j = 0; j < 19; j++) anc[i][j] = 0;
		d[i] = 0;		
	}
}

int cnt;
 
void dfs(int u, int p){
	cnt++;
	le[u] = cnt;
	for(auto v : Adj[u]){
		if(v == p) continue;
		d[v] = d[u] + 1;
		anc[v][0] = u;
		for(int i = 1; i <= 19; i++) anc[v][i] = anc[anc[v][i - 1]][i - 1];
		dfs(v, u);
	}
	ri[u] = cnt;
}
 
int lca(int x, int y){
	if(d[x] > d[y]) swap(x, y);
	for(int i = 19; i >= 0; i--) if((d[y] - d[x]) >= (1LL << i)) y = anc[y][i];
	if(x == y) return x;
	for(int i = 19; i >= 0; i--){
		if(anc[x][i] != anc[y][i]){
			x = anc[x][i], y = anc[y][i];
		}
	}
	return anc[x][0];
}
 
int dist(int x, int y){
	return d[x] + d[y] - 2 * d[lca(x, y)];
}
 
bool in(int a, int b, int c){
	//return (dist(a, c) + dist(b, c) == dist(a, b));
	int mn = min(le[a], le[b]), mx = max(le[a], le[b]);
	if(mn <= le[c] && mx >= le[c] && mx <= ri[c]) return 1;
	if(mn >= le[c] && mn <= ri[c] && mx > ri[c]) return 1;
	return 0;
}
 
int st[N], en[N];
 
void process(){
    cin >> n;
    init();
    for(int i = 1; i < n; i++){
    	int x, y;
    	cin >> x >> y;
    	Adj[x].pb(y);
    	Adj[y].pb(x);
	}
	cin >> m;
	dfs(1, 1);
	for(int i = 1; i <= m; i++) cin >> st[i] >> en[i];
	for(int i = 1; i <= m; i++){
		for(int j = i + 1; j <= m; j++){
			assert(st[i] != st[j]);
			assert(en[i] != en[j]);
			bool ck1 = in(st[i], en[i], st[j]);
			bool ck2 = in(st[i], en[i], en[j]);
			bool ck3 = in(st[j], en[j], st[i]);
			bool ck4 = in(st[j], en[j], en[i]);
			//cout << ck1 << " " << ck2 << " " << ck3 << " " << ck4 << "\n";
			bool temp1 = (ck1 | ck4), temp2 = (ck2 | ck3);
			if(temp1 & temp2){
				cout << "No\n";
				return;
			}
			if(temp1){
				Adj2[j].pb(i);
				deg[i]++;
			}
			if(temp2){
				Adj2[i].pb(j);
				deg[j]++;
			}
		}
	}
	queue<int> q;
	for(int i = 1; i <= m; i++) if(!deg[i]) q.push(i);
	int cnt = 0;
	while(!q.empty()){
		cnt++;
		int u = q.front();
		//cout << u << "\n";
		q.pop();
		for(auto v : Adj2[u]){
			deg[v]--;
			if(!deg[v]) q.push(v);
		}
	}
	if(cnt == m) cout << "Yes\n";
	else cout << "No\n";
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    //freopen("KEK.inp", "r", stdin);
    //freopen("KEK.out", "w", stdout);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--) process();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23