oj.uz

Submission #552158

# Submission time Handle Problem Language Result Execution time Memory
552158 2022-04-22T14:21:49 Z errorgorn Jail (JOI22_jail) C++17
0 / 100
 2202 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[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 59 ms 120520 KB Output is correct
2 Correct 72 ms 120668 KB Output is correct
3 Correct 60 ms 120528 KB Output is correct
4 Correct 117 ms 120716 KB Output is correct
5 Correct 108 ms 120604 KB Output is correct
6 Correct 64 ms 120832 KB Output is correct
7 Correct 66 ms 120848 KB Output is correct
8 Correct 62 ms 121212 KB Output is correct
9 Correct 577 ms 180964 KB Output is correct
10 Runtime error 2202 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 56 ms 120524 KB Output is correct
2 Correct 62 ms 120564 KB Output is correct
3 Correct 63 ms 120856 KB Output is correct
4 Correct 66 ms 120964 KB Output is correct
5 Incorrect 73 ms 120836 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 120524 KB Output is correct
2 Correct 62 ms 120564 KB Output is correct
3 Correct 63 ms 120856 KB Output is correct
4 Correct 66 ms 120964 KB Output is correct
5 Incorrect 73 ms 120836 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 120524 KB Output is correct
2 Correct 62 ms 120564 KB Output is correct
3 Correct 63 ms 120856 KB Output is correct
4 Correct 66 ms 120964 KB Output is correct
5 Incorrect 73 ms 120836 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 120524 KB Output is correct
2 Correct 62 ms 120564 KB Output is correct
3 Correct 63 ms 120856 KB Output is correct
4 Correct 66 ms 120964 KB Output is correct
5 Incorrect 73 ms 120836 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 120476 KB Output is correct
2 Correct 72 ms 120532 KB Output is correct
3 Correct 69 ms 120572 KB Output is correct
4 Correct 60 ms 120468 KB Output is correct
5 Correct 69 ms 120692 KB Output is correct
6 Correct 61 ms 120660 KB Output is correct
7 Correct 60 ms 120712 KB Output is correct
8 Correct 60 ms 120528 KB Output is correct
9 Correct 68 ms 120536 KB Output is correct
10 Correct 68 ms 120676 KB Output is correct
11 Correct 58 ms 120552 KB Output is correct
12 Incorrect 69 ms 120816 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 120520 KB Output is correct
2 Correct 72 ms 120668 KB Output is correct
3 Correct 60 ms 120528 KB Output is correct
4 Correct 117 ms 120716 KB Output is correct
5 Correct 108 ms 120604 KB Output is correct
6 Correct 64 ms 120832 KB Output is correct
7 Correct 66 ms 120848 KB Output is correct
8 Correct 62 ms 121212 KB Output is correct
9 Correct 577 ms 180964 KB Output is correct
10 Runtime error 2202 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -