oj.uz

Submission #552162

# Submission time Handle Problem Language Result Execution time Memory
552162 2022-04-22T14:26:11 Z errorgorn Jail (JOI22_jail) C++17
0 / 100
 2215 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].pub(idx[it][x].fi);
			al2[IDX].pub(idx[curr][x].fi);
			IDX++;
			
			idx[it][x+1].se=IDX;
			al2[IDX].clear();
			al2[idx[it][x].se].pub(IDX);
			al2[idx[curr][x].se].pub(IDX);
			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[i].pub(idx[curr][0].fi);
					al2[idx[curr][0].se].pub(i);
					curr=tkd[curr][0];
				}
			}
			if (b!=g){
				int curr=tkd[b][0];
				while (curr!=g){
					al2[i].pub(idx[curr][0].fi);
					al2[idx[curr][0].se].pub(i);
					curr=tkd[curr][0];
				}
			}
			
			if (g!=a && g!=b){
				al2[i].pub(idx[g][0].fi);
				al2[idx[g][0].se].pub(i);
			}
		}
		
		// 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 57 ms 120524 KB Output is correct
2 Correct 58 ms 120448 KB Output is correct
3 Correct 58 ms 120440 KB Output is correct
4 Correct 83 ms 120720 KB Output is correct
5 Correct 106 ms 120660 KB Output is correct
6 Correct 59 ms 120860 KB Output is correct
7 Correct 60 ms 120884 KB Output is correct
8 Correct 61 ms 121184 KB Output is correct
9 Correct 566 ms 180284 KB Output is correct
10 Runtime error 2215 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 57 ms 120560 KB Output is correct
2 Correct 61 ms 120688 KB Output is correct
3 Correct 62 ms 120744 KB Output is correct
4 Correct 66 ms 120852 KB Output is correct
5 Incorrect 59 ms 120752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 120560 KB Output is correct
2 Correct 61 ms 120688 KB Output is correct
3 Correct 62 ms 120744 KB Output is correct
4 Correct 66 ms 120852 KB Output is correct
5 Incorrect 59 ms 120752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 120560 KB Output is correct
2 Correct 61 ms 120688 KB Output is correct
3 Correct 62 ms 120744 KB Output is correct
4 Correct 66 ms 120852 KB Output is correct
5 Incorrect 59 ms 120752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 120560 KB Output is correct
2 Correct 61 ms 120688 KB Output is correct
3 Correct 62 ms 120744 KB Output is correct
4 Correct 66 ms 120852 KB Output is correct
5 Incorrect 59 ms 120752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 120452 KB Output is correct
2 Correct 68 ms 120480 KB Output is correct
3 Correct 56 ms 120524 KB Output is correct
4 Correct 58 ms 120456 KB Output is correct
5 Correct 65 ms 120532 KB Output is correct
6 Correct 58 ms 120652 KB Output is correct
7 Correct 60 ms 120708 KB Output is correct
8 Correct 58 ms 120472 KB Output is correct
9 Correct 58 ms 120524 KB Output is correct
10 Correct 57 ms 120564 KB Output is correct
11 Correct 57 ms 120584 KB Output is correct
12 Incorrect 59 ms 120824 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 120524 KB Output is correct
2 Correct 58 ms 120448 KB Output is correct
3 Correct 58 ms 120440 KB Output is correct
4 Correct 83 ms 120720 KB Output is correct
5 Correct 106 ms 120660 KB Output is correct
6 Correct 59 ms 120860 KB Output is correct
7 Correct 60 ms 120884 KB Output is correct
8 Correct 61 ms 121184 KB Output is correct
9 Correct 566 ms 180284 KB Output is correct
10 Runtime error 2215 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -