oj.uz

답안 #633702

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633702 2022-08-23T06:02:22 Z S2speed Jail (JOI22_jail) C++17
0 / 100
 131 ms 237992 KB 
#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] - 1) continue;
			jda[i].push_back(lb[v][j][1]); adj[lb[v][j][1]].push_back(i);
			v = u;
		}
		v = jad[a[i]][0];
		for(ll j = 19 ; ~j ; j--){
			ll u = jad[v][j];
			if(u == -1) continue;
			if(dis[u] < dis[l] - 1) continue;
			adj[i].push_back(lb[v][j][0]); jda[lb[v][j][0]].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] - 1) 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 ; j--){
			ll u = jad[v][j];
			if(u == -1) continue;
			if(dis[u] < dis[l] - 1) continue;
			adj[i].push_back(lb[v][j][0]); jda[lb[v][j][0]].push_back(i);
			v = u;
		}
		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;
}

/*
1
4
1 2
2 3
3 4
2
2 1
3 2
*/

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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 237976 KB Output is correct
2 Correct 120 ms 237896 KB Output is correct
3 Incorrect 109 ms 237992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 237956 KB Output is correct
2 Incorrect 114 ms 237876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 237956 KB Output is correct
2 Incorrect 114 ms 237876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 237956 KB Output is correct
2 Incorrect 114 ms 237876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 237956 KB Output is correct
2 Incorrect 114 ms 237876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 237956 KB Output is correct
2 Correct 125 ms 237928 KB Output is correct
3 Correct 110 ms 237880 KB Output is correct
4 Incorrect 131 ms 237904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 237976 KB Output is correct
2 Correct 120 ms 237896 KB Output is correct
3 Incorrect 109 ms 237992 KB Output isn't correct
4 Halted 0 ms 0 KB -