oj.uz

Submission #552156

# Submission time Handle Problem Language Result Execution time Memory
552156 2022-04-22T14:19:35 Z errorgorn Jail (JOI22_jail) C++17
0 / 100
 2204 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 54 ms 120484 KB Output is correct
2 Correct 56 ms 120472 KB Output is correct
3 Correct 58 ms 120560 KB Output is correct
4 Correct 81 ms 120784 KB Output is correct
5 Correct 103 ms 120744 KB Output is correct
6 Correct 59 ms 120908 KB Output is correct
7 Correct 58 ms 120864 KB Output is correct
8 Correct 59 ms 121264 KB Output is correct
9 Correct 598 ms 180724 KB Output is correct
10 Runtime error 2204 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 120524 KB Output is correct
2 Correct 63 ms 120568 KB Output is correct
3 Correct 73 ms 121028 KB Output is correct
4 Correct 66 ms 120864 KB Output is correct
5 Incorrect 64 ms 120792 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 120524 KB Output is correct
2 Correct 63 ms 120568 KB Output is correct
3 Correct 73 ms 121028 KB Output is correct
4 Correct 66 ms 120864 KB Output is correct
5 Incorrect 64 ms 120792 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 120524 KB Output is correct
2 Correct 63 ms 120568 KB Output is correct
3 Correct 73 ms 121028 KB Output is correct
4 Correct 66 ms 120864 KB Output is correct
5 Incorrect 64 ms 120792 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 120524 KB Output is correct
2 Correct 63 ms 120568 KB Output is correct
3 Correct 73 ms 121028 KB Output is correct
4 Correct 66 ms 120864 KB Output is correct
5 Incorrect 64 ms 120792 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 120472 KB Output is correct
2 Correct 78 ms 120524 KB Output is correct
3 Correct 62 ms 120504 KB Output is correct
4 Correct 63 ms 120448 KB Output is correct
5 Correct 70 ms 120732 KB Output is correct
6 Correct 64 ms 120780 KB Output is correct
7 Correct 64 ms 120652 KB Output is correct
8 Correct 63 ms 120648 KB Output is correct
9 Correct 63 ms 120552 KB Output is correct
10 Correct 63 ms 120672 KB Output is correct
11 Correct 64 ms 120584 KB Output is correct
12 Incorrect 64 ms 120812 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 120484 KB Output is correct
2 Correct 56 ms 120472 KB Output is correct
3 Correct 58 ms 120560 KB Output is correct
4 Correct 81 ms 120784 KB Output is correct
5 Correct 103 ms 120744 KB Output is correct
6 Correct 59 ms 120908 KB Output is correct
7 Correct 58 ms 120864 KB Output is correct
8 Correct 59 ms 121264 KB Output is correct
9 Correct 598 ms 180724 KB Output is correct
10 Runtime error 2204 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -