oj.uz

Submission #737746

# Submission time Handle Problem Language Result Execution time Memory
737746 2023-05-07T16:54:41 Z myrcella Jail (JOI22_jail) C++17
0 / 100
 126 ms 169804 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 2e5+10;

int n,m;
vector <int> edge[maxn];
vector <int> ne[maxn + maxn*17*2];//[0,m): paths, [m,m+n): starts at i, [m+n,m+n+n): ends at i
int fa[maxn][17],dep[maxn];
pii path[maxn];
int deg[maxn];

void adde(int u,int v) {
//	if (u<m or v<m) debug(u),debug(v);
	ne[u].pb(v);
	deg[v]++;
}

void dfs(int u,int lst) {
	fa[u][0] = lst;
	dep[u] = lst==-1?0:dep[lst]+1;
	rep(i,1,17) {
		if (fa[u][i-1]==-1) break;
		adde(m+u*17+i-1,m+u*17+i);
		adde(m+n*17+u*17+i-1,m+n*17+u*17+i);
		adde(m+fa[u][i-1]*17+i-1,m+u*17+i);
		adde(m+n*17+fa[u][i-1]*17+i-1,m+n*17+u*17+i);
		fa[u][i] = fa[fa[u][i-1]][i-1];
	}
	for (int v:edge[u]) {
		if (v==lst) continue;
		dfs(v,u);
	}
}

void update(int pathid,int u,int v) { //exclude u,v
	bool uu=false,vv=false;
	if (dep[u]>dep[v]) uu=true, u = fa[u][0];
	else if (dep[u]<dep[v]) vv=true, v=fa[v][0];
	if (dep[u]<dep[v]) swap(u,v);
	for (int i=16;i>=0;i--) {
		if (dep[u] - (1<<i) >= dep[v]) {
			adde(m+u*17+i,pathid);
			adde(pathid,m+n*17+u*17+i);
			u = fa[u][i];
		}
	}
	if (u==v) return;
	if (vv==false) v=fa[v][0],adde(m+v*17,pathid),adde(pathid,m+n*17+v*17);
	if (uu==false) u=fa[u][0],adde(m+u*17,pathid),adde(pathid,m+n*17+u*17);
	if (dep[u]>dep[v]) u=fa[u][0],adde(m+u*17,pathid),adde(pathid,m+n*17+u*17);
	if (dep[v]>dep[u]) v=fa[v][0],adde(m+v*17,pathid),adde(pathid,m+n*17+v*17);
	for (int i=16;i>=0;i--) if (fa[u][i]!=fa[v][i]) {
		adde(m+u*17+i,pathid);
		adde(pathid,m+n*17+u*17+i);
		u = fa[u][i];
		adde(m+v*17+i,pathid);
		adde(pathid,m+n*17+v*17+i);
		v = fa[v][i];
	}
	adde(m+u*17,pathid);
	adde(pathid,m+n*17+u*17);
	adde(m+v*17+1,pathid);
	adde(pathid,m+n*17+v*17+1);
}



void solve() {
	cin>>n;
	rep(i,0,n)
		rep(j,0,17) fa[i][j]=-1;
	rep(i,1,n) {
		int u,v;
		cin>>u>>v;
		u--,v--;
		edge[u].pb(v);
		edge[v].pb(u);
	}	
	cin>>m;dfs(0,-1);
	rep(i,0,m) {
		cin>>path[i].fi>>path[i].se;
		path[i].fi--,path[i].se--;
		adde(i,m+path[i].fi*17);
		adde(i,m+n*17+path[i].se*17);
		update(i,path[i].fi,path[i].se);
		adde(m+path[i].se*17,i);
		adde(i,m+n*17+path[i].fi*17);
	}
	
	queue <int> q;
	rep(i,0,m+n*17*2) if (deg[i]==0) q.push(i);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int v:ne[u]) {
			deg[v]--;
			if (deg[v]==0)q.push(v);
		}
	}
	bool ok = true;
	rep(i,0,m+n*17*2) {
		if (deg[i]!=0) ok=false,deg[i]=0;
		while (!ne[i].empty()) ne[i].pop_back();
		if (i<n) while (!edge[i].empty()) edge[i].pop_back();
	}
	if (ok) cout<<"Yes\n";
	else cout<<"No\n";
	return;
	
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	int _;cin>>_;
	while (_--) solve();
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 169340 KB Output is correct
2 Correct 82 ms 169404 KB Output is correct
3 Correct 80 ms 169320 KB Output is correct
4 Incorrect 126 ms 169804 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 169404 KB Output is correct
2 Correct 81 ms 169320 KB Output is correct
3 Incorrect 85 ms 169680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 169404 KB Output is correct
2 Correct 81 ms 169320 KB Output is correct
3 Incorrect 85 ms 169680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 169404 KB Output is correct
2 Correct 81 ms 169320 KB Output is correct
3 Incorrect 85 ms 169680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 169404 KB Output is correct
2 Correct 81 ms 169320 KB Output is correct
3 Incorrect 85 ms 169680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 169424 KB Output is correct
2 Correct 95 ms 169424 KB Output is correct
3 Correct 81 ms 169504 KB Output is correct
4 Correct 77 ms 169412 KB Output is correct
5 Incorrect 91 ms 169504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 169340 KB Output is correct
2 Correct 82 ms 169404 KB Output is correct
3 Correct 80 ms 169320 KB Output is correct
4 Incorrect 126 ms 169804 KB Output isn't correct
5 Halted 0 ms 0 KB -