oj.uz

Submission #633712

# Submission time Handle Problem Language Result Execution time Memory
633712 2022-08-23T06:43:44 Z S2speed Jail (JOI22_jail) C++17
5 / 100
 4290 ms 809608 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]) continue;
			adj[i].push_back(lb[v][j][0]); jda[lb[v][j][0]].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]) continue;
			jda[i].push_back(lb[v][j][1]); adj[lb[v][j][1]].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]) 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]) continue;
			adj[i].push_back(lb[v][j][0]); jda[lb[v][j][0]].push_back(i);
			v = u;
		}
		if(l != a[i]){
			jda[i].push_back(lb[l][0][1]); adj[lb[l][0][1]].push_back(i);
		}
		if(l != b[i]){
			adj[i].push_back(lb[l][0][0]); jda[lb[l][0][0]].push_back(i);
		}
		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;
}
 
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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 237896 KB Output is correct
2 Correct 124 ms 238004 KB Output is correct
3 Correct 133 ms 238028 KB Output is correct
4 Correct 175 ms 238552 KB Output is correct
5 Correct 239 ms 239000 KB Output is correct
6 Correct 129 ms 238464 KB Output is correct
7 Correct 119 ms 238428 KB Output is correct
8 Correct 124 ms 238632 KB Output is correct
9 Correct 799 ms 256620 KB Output is correct
10 Correct 2225 ms 622712 KB Output is correct
11 Correct 147 ms 238136 KB Output is correct
12 Correct 274 ms 239312 KB Output is correct
13 Correct 2253 ms 650516 KB Output is correct
14 Correct 2169 ms 650836 KB Output is correct
15 Correct 3156 ms 699400 KB Output is correct
16 Correct 4290 ms 809608 KB Output is correct
17 Correct 2534 ms 682032 KB Output is correct
18 Correct 2090 ms 645156 KB Output is correct
19 Correct 2457 ms 671192 KB Output is correct
20 Correct 2410 ms 671156 KB Output is correct
21 Correct 2789 ms 716880 KB Output is correct
22 Correct 1905 ms 633748 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 238084 KB Output is correct
2 Correct 116 ms 237992 KB Output is correct
3 Correct 140 ms 238484 KB Output is correct
4 Correct 118 ms 238608 KB Output is correct
5 Incorrect 120 ms 238436 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 238084 KB Output is correct
2 Correct 116 ms 237992 KB Output is correct
3 Correct 140 ms 238484 KB Output is correct
4 Correct 118 ms 238608 KB Output is correct
5 Incorrect 120 ms 238436 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 238084 KB Output is correct
2 Correct 116 ms 237992 KB Output is correct
3 Correct 140 ms 238484 KB Output is correct
4 Correct 118 ms 238608 KB Output is correct
5 Incorrect 120 ms 238436 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 238084 KB Output is correct
2 Correct 116 ms 237992 KB Output is correct
3 Correct 140 ms 238484 KB Output is correct
4 Correct 118 ms 238608 KB Output is correct
5 Incorrect 120 ms 238436 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 237924 KB Output is correct
2 Correct 127 ms 237964 KB Output is correct
3 Correct 116 ms 237960 KB Output is correct
4 Correct 136 ms 238168 KB Output is correct
5 Correct 132 ms 238144 KB Output is correct
6 Incorrect 116 ms 238180 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 237896 KB Output is correct
2 Correct 124 ms 238004 KB Output is correct
3 Correct 133 ms 238028 KB Output is correct
4 Correct 175 ms 238552 KB Output is correct
5 Correct 239 ms 239000 KB Output is correct
6 Correct 129 ms 238464 KB Output is correct
7 Correct 119 ms 238428 KB Output is correct
8 Correct 124 ms 238632 KB Output is correct
9 Correct 799 ms 256620 KB Output is correct
10 Correct 2225 ms 622712 KB Output is correct
11 Correct 147 ms 238136 KB Output is correct
12 Correct 274 ms 239312 KB Output is correct
13 Correct 2253 ms 650516 KB Output is correct
14 Correct 2169 ms 650836 KB Output is correct
15 Correct 3156 ms 699400 KB Output is correct
16 Correct 4290 ms 809608 KB Output is correct
17 Correct 2534 ms 682032 KB Output is correct
18 Correct 2090 ms 645156 KB Output is correct
19 Correct 2457 ms 671192 KB Output is correct
20 Correct 2410 ms 671156 KB Output is correct
21 Correct 2789 ms 716880 KB Output is correct
22 Correct 1905 ms 633748 KB Output is correct
23 Correct 115 ms 238084 KB Output is correct
24 Correct 116 ms 237992 KB Output is correct
25 Correct 140 ms 238484 KB Output is correct
26 Correct 118 ms 238608 KB Output is correct
27 Incorrect 120 ms 238436 KB Output isn't correct
28 Halted 0 ms 0 KB -