oj.uz

Submission #552157

# Submission time Handle Problem Language Result Execution time Memory
552157 2022-04-22T14:20:18 Z errorgorn Jail (JOI22_jail) C++17
60 / 100
 2274 ms 1048576 KB 
// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
 
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
 
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
 
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
int n,q;
vector<int> al[120005];
 
int d[120005];
int tkd[120005][19];
ii idx[120005][19];
vector<int> al2[5000005];
int IDX;
 
void dfs(int i,int p){
	for (auto it:al[i]){
		if (it==p) continue;
		
		d[it]=d[i]+1;
		int curr=tkd[it][0]=i;
		
		idx[it][0]={IDX,IDX+1};
		al2[IDX++].clear();
		al2[IDX++].clear();
		
		rep(x,0,19){
			if (tkd[curr][x]==-1) continue;
			curr=tkd[it][x+1]=tkd[curr][x];
			
			// idx[it][x+1].fi=IDX;
			// al2[IDX].clear();
			// al2[idx[it][x].fi].pub(IDX);
			// al2[idx[curr][x].fi].pub(IDX);
			// IDX++;
// 			
			// idx[it][x+1].se=IDX;
			// al2[IDX].clear();
			// al2[IDX].pub(idx[it][x].se);
			// al2[IDX].pub(idx[curr][x].se);
			// IDX++;
		}
		
		dfs(it,i);
	}
}
 
int mov(int i,int k){
	rep(x,0,19) if (k&(1<<x)) i=tkd[i][x];
	return i;
}
 
int lca(int i,int j){
	if (d[i]<d[j]) swap(i,j);
	i=mov(i,d[i]-d[j]);
	if (i==j) return i;
	
	rep(x,19,0) if (tkd[i][x]!=tkd[j][x]){
		i=tkd[i][x];
		j=tkd[j][x];
	}
	
	return tkd[i][0];
}
 
int dist(int i,int j){
	int g=lca(i,j);
	return d[i]+d[j]-2*d[g];
}
 
int vis[5000005];
bool cyc;
void dfs2(int i){
	vis[i]=1;
	
	for (auto it:al2[i]){
		if (vis[it]==1) cyc=true;
		if (vis[it]==0) dfs2(it);
	}
	
	vis[i]=2;
}
 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n;
		
		rep(x,1,n+1) al[x].clear();
		
		int a,b;
		rep(x,1,n){
			cin>>a>>b;
			al[a].pub(b);
			al[b].pub(a);
		}
		cin>>q;
		
		rep(x,0,q) al2[x].clear();
		IDX=q;
		
		idx[1][0]={IDX,IDX+1};
		al2[IDX++].clear();
		al2[IDX++].clear();
		
		rep(x,1,n+1) rep(y,0,19) tkd[x][y]=-1;
		dfs(1,-1);
		
		//rep(x,1,n+1) cout<<idx[x][0].fi<<" "<<idx[x][0].se<<endl;
		
		rep(i,0,q){
			cin>>a>>b;
			al2[i].pub(idx[a][0].fi);
			al2[i].pub(idx[a][0].se);
			al2[idx[b][0].fi].pub(i);
			al2[idx[b][0].se].pub(i);
			
			int g=lca(a,b);
			
			if (a!=g){
				int curr=tkd[a][0];
				while (curr!=g){
					al2[idx[curr][0].fi].pub(i);
					al2[i].pub(idx[curr][0].se);
					curr=tkd[curr][0];
				}
			}
			if (b!=g){
				int curr=tkd[b][0];
				while (curr!=g){
					al2[idx[curr][0].fi].pub(i);
					al2[i].pub(idx[curr][0].se);
					curr=tkd[curr][0];
				}
			}
			
			if (g!=a && g!=b){
				al2[idx[g][0].fi].pub(i);
				al2[i].pub(idx[g][0].se);
			}
		}
		
		// rep(x,0,IDX){
			// for (auto y:al2[x]) cout<<x<<" "<<y<<endl;
		// }
		
		cyc=false;
		rep(x,0,IDX) vis[x]=0;
		rep(x,0,IDX) if (vis[x]==0) dfs2(x);
		
		if (!cyc) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 120560 KB Output is correct
2 Correct 58 ms 120572 KB Output is correct
3 Correct 58 ms 120540 KB Output is correct
4 Correct 69 ms 120780 KB Output is correct
5 Correct 92 ms 120692 KB Output is correct
6 Correct 61 ms 120676 KB Output is correct
7 Correct 59 ms 120692 KB Output is correct
8 Correct 58 ms 121116 KB Output is correct
9 Correct 307 ms 175692 KB Output is correct
10 Runtime error 2266 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 120492 KB Output is correct
2 Correct 64 ms 120528 KB Output is correct
3 Correct 68 ms 120708 KB Output is correct
4 Correct 58 ms 120616 KB Output is correct
5 Correct 60 ms 120636 KB Output is correct
6 Correct 59 ms 120652 KB Output is correct
7 Correct 60 ms 120672 KB Output is correct
8 Correct 67 ms 120780 KB Output is correct
9 Correct 59 ms 120732 KB Output is correct
10 Correct 58 ms 120652 KB Output is correct
11 Correct 60 ms 120736 KB Output is correct
12 Correct 75 ms 120712 KB Output is correct
13 Correct 58 ms 120700 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 120492 KB Output is correct
2 Correct 64 ms 120528 KB Output is correct
3 Correct 68 ms 120708 KB Output is correct
4 Correct 58 ms 120616 KB Output is correct
5 Correct 60 ms 120636 KB Output is correct
6 Correct 59 ms 120652 KB Output is correct
7 Correct 60 ms 120672 KB Output is correct
8 Correct 67 ms 120780 KB Output is correct
9 Correct 59 ms 120732 KB Output is correct
10 Correct 58 ms 120652 KB Output is correct
11 Correct 60 ms 120736 KB Output is correct
12 Correct 75 ms 120712 KB Output is correct
13 Correct 58 ms 120700 KB Output is correct
14 Correct 57 ms 120524 KB Output is correct
15 Correct 60 ms 120544 KB Output is correct
16 Correct 62 ms 120748 KB Output is correct
17 Correct 69 ms 120636 KB Output is correct
18 Correct 59 ms 120732 KB Output is correct
19 Correct 57 ms 120508 KB Output is correct
20 Correct 59 ms 120696 KB Output is correct
21 Correct 63 ms 120652 KB Output is correct
22 Correct 64 ms 120772 KB Output is correct
23 Correct 58 ms 120472 KB Output is correct
24 Correct 59 ms 120524 KB Output is correct
25 Correct 58 ms 120732 KB Output is correct
26 Correct 59 ms 120620 KB Output is correct
27 Correct 62 ms 120756 KB Output is correct
28 Correct 70 ms 120460 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 120492 KB Output is correct
2 Correct 64 ms 120528 KB Output is correct
3 Correct 68 ms 120708 KB Output is correct
4 Correct 58 ms 120616 KB Output is correct
5 Correct 60 ms 120636 KB Output is correct
6 Correct 59 ms 120652 KB Output is correct
7 Correct 60 ms 120672 KB Output is correct
8 Correct 67 ms 120780 KB Output is correct
9 Correct 59 ms 120732 KB Output is correct
10 Correct 58 ms 120652 KB Output is correct
11 Correct 60 ms 120736 KB Output is correct
12 Correct 75 ms 120712 KB Output is correct
13 Correct 58 ms 120700 KB Output is correct
14 Correct 57 ms 120524 KB Output is correct
15 Correct 60 ms 120544 KB Output is correct
16 Correct 62 ms 120748 KB Output is correct
17 Correct 69 ms 120636 KB Output is correct
18 Correct 59 ms 120732 KB Output is correct
19 Correct 57 ms 120508 KB Output is correct
20 Correct 59 ms 120696 KB Output is correct
21 Correct 63 ms 120652 KB Output is correct
22 Correct 64 ms 120772 KB Output is correct
23 Correct 58 ms 120472 KB Output is correct
24 Correct 59 ms 120524 KB Output is correct
25 Correct 58 ms 120732 KB Output is correct
26 Correct 59 ms 120620 KB Output is correct
27 Correct 62 ms 120756 KB Output is correct
28 Correct 70 ms 120460 KB Output is correct
29 Correct 67 ms 121128 KB Output is correct
30 Correct 58 ms 120784 KB Output is correct
31 Correct 62 ms 120892 KB Output is correct
32 Correct 60 ms 120692 KB Output is correct
33 Correct 60 ms 120640 KB Output is correct
34 Correct 72 ms 120688 KB Output is correct
35 Correct 66 ms 120952 KB Output is correct
36 Correct 62 ms 120692 KB Output is correct
37 Correct 58 ms 120776 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 120492 KB Output is correct
2 Correct 64 ms 120528 KB Output is correct
3 Correct 68 ms 120708 KB Output is correct
4 Correct 58 ms 120616 KB Output is correct
5 Correct 60 ms 120636 KB Output is correct
6 Correct 59 ms 120652 KB Output is correct
7 Correct 60 ms 120672 KB Output is correct
8 Correct 67 ms 120780 KB Output is correct
9 Correct 59 ms 120732 KB Output is correct
10 Correct 58 ms 120652 KB Output is correct
11 Correct 60 ms 120736 KB Output is correct
12 Correct 75 ms 120712 KB Output is correct
13 Correct 58 ms 120700 KB Output is correct
14 Correct 57 ms 120524 KB Output is correct
15 Correct 60 ms 120544 KB Output is correct
16 Correct 62 ms 120748 KB Output is correct
17 Correct 69 ms 120636 KB Output is correct
18 Correct 59 ms 120732 KB Output is correct
19 Correct 57 ms 120508 KB Output is correct
20 Correct 59 ms 120696 KB Output is correct
21 Correct 63 ms 120652 KB Output is correct
22 Correct 64 ms 120772 KB Output is correct
23 Correct 58 ms 120472 KB Output is correct
24 Correct 59 ms 120524 KB Output is correct
25 Correct 58 ms 120732 KB Output is correct
26 Correct 59 ms 120620 KB Output is correct
27 Correct 62 ms 120756 KB Output is correct
28 Correct 70 ms 120460 KB Output is correct
29 Correct 67 ms 121128 KB Output is correct
30 Correct 58 ms 120784 KB Output is correct
31 Correct 62 ms 120892 KB Output is correct
32 Correct 60 ms 120692 KB Output is correct
33 Correct 60 ms 120640 KB Output is correct
34 Correct 72 ms 120688 KB Output is correct
35 Correct 66 ms 120952 KB Output is correct
36 Correct 62 ms 120692 KB Output is correct
37 Correct 58 ms 120776 KB Output is correct
38 Correct 328 ms 175476 KB Output is correct
39 Runtime error 2274 ms 1048576 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 120448 KB Output is correct
2 Correct 60 ms 120568 KB Output is correct
3 Correct 60 ms 120524 KB Output is correct
4 Correct 60 ms 120460 KB Output is correct
5 Correct 64 ms 120600 KB Output is correct
6 Correct 62 ms 120704 KB Output is correct
7 Correct 71 ms 120652 KB Output is correct
8 Correct 66 ms 120520 KB Output is correct
9 Correct 57 ms 120528 KB Output is correct
10 Correct 65 ms 120576 KB Output is correct
11 Correct 61 ms 120572 KB Output is correct
12 Correct 60 ms 120692 KB Output is correct
13 Correct 96 ms 120908 KB Output is correct
14 Correct 93 ms 120800 KB Output is correct
15 Correct 103 ms 120756 KB Output is correct
16 Correct 197 ms 186580 KB Output is correct
17 Correct 387 ms 209268 KB Output is correct
18 Correct 678 ms 244544 KB Output is correct
19 Correct 248 ms 191512 KB Output is correct
20 Correct 224 ms 191516 KB Output is correct
21 Correct 239 ms 191676 KB Output is correct
22 Correct 363 ms 209596 KB Output is correct
23 Correct 265 ms 208304 KB Output is correct
24 Correct 302 ms 209824 KB Output is correct
25 Correct 281 ms 210516 KB Output is correct
26 Correct 305 ms 210524 KB Output is correct
27 Correct 323 ms 199804 KB Output is correct
28 Correct 335 ms 208264 KB Output is correct
29 Correct 328 ms 202212 KB Output is correct
30 Correct 278 ms 193472 KB Output is correct
31 Correct 262 ms 194536 KB Output is correct
32 Correct 240 ms 193484 KB Output is correct
33 Correct 281 ms 196456 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 120560 KB Output is correct
2 Correct 58 ms 120572 KB Output is correct
3 Correct 58 ms 120540 KB Output is correct
4 Correct 69 ms 120780 KB Output is correct
5 Correct 92 ms 120692 KB Output is correct
6 Correct 61 ms 120676 KB Output is correct
7 Correct 59 ms 120692 KB Output is correct
8 Correct 58 ms 121116 KB Output is correct
9 Correct 307 ms 175692 KB Output is correct
10 Runtime error 2266 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -