oj.uz

Submission #552163

# Submission time Handle Problem Language Result Execution time Memory
552163 2022-04-22T14:28:09 Z errorgorn Jail (JOI22_jail) C++17
60 / 100
 2404 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;
			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++;
			
			curr=tkd[it][x+1];
		}
		
		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 120532 KB Output is correct
2 Correct 56 ms 120576 KB Output is correct
3 Correct 59 ms 120540 KB Output is correct
4 Correct 86 ms 120700 KB Output is correct
5 Correct 118 ms 120592 KB Output is correct
6 Correct 59 ms 120976 KB Output is correct
7 Correct 60 ms 120780 KB Output is correct
8 Correct 64 ms 121212 KB Output is correct
9 Correct 564 ms 180484 KB Output is correct
10 Runtime error 2391 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 57 ms 120556 KB Output is correct
2 Correct 65 ms 120476 KB Output is correct
3 Correct 67 ms 120860 KB Output is correct
4 Correct 64 ms 120728 KB Output is correct
5 Correct 58 ms 120780 KB Output is correct
6 Correct 68 ms 120824 KB Output is correct
7 Correct 60 ms 120844 KB Output is correct
8 Correct 62 ms 120728 KB Output is correct
9 Correct 60 ms 120776 KB Output is correct
10 Correct 62 ms 120840 KB Output is correct
11 Correct 63 ms 120764 KB Output is correct
12 Correct 57 ms 120628 KB Output is correct
13 Correct 70 ms 120752 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 120556 KB Output is correct
2 Correct 65 ms 120476 KB Output is correct
3 Correct 67 ms 120860 KB Output is correct
4 Correct 64 ms 120728 KB Output is correct
5 Correct 58 ms 120780 KB Output is correct
6 Correct 68 ms 120824 KB Output is correct
7 Correct 60 ms 120844 KB Output is correct
8 Correct 62 ms 120728 KB Output is correct
9 Correct 60 ms 120776 KB Output is correct
10 Correct 62 ms 120840 KB Output is correct
11 Correct 63 ms 120764 KB Output is correct
12 Correct 57 ms 120628 KB Output is correct
13 Correct 70 ms 120752 KB Output is correct
14 Correct 61 ms 120480 KB Output is correct
15 Correct 62 ms 120536 KB Output is correct
16 Correct 60 ms 120872 KB Output is correct
17 Correct 59 ms 120748 KB Output is correct
18 Correct 61 ms 120796 KB Output is correct
19 Correct 71 ms 120500 KB Output is correct
20 Correct 63 ms 120780 KB Output is correct
21 Correct 60 ms 120836 KB Output is correct
22 Correct 59 ms 120860 KB Output is correct
23 Correct 64 ms 120472 KB Output is correct
24 Correct 58 ms 120652 KB Output is correct
25 Correct 64 ms 120876 KB Output is correct
26 Correct 61 ms 120796 KB Output is correct
27 Correct 59 ms 120712 KB Output is correct
28 Correct 57 ms 120580 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 120556 KB Output is correct
2 Correct 65 ms 120476 KB Output is correct
3 Correct 67 ms 120860 KB Output is correct
4 Correct 64 ms 120728 KB Output is correct
5 Correct 58 ms 120780 KB Output is correct
6 Correct 68 ms 120824 KB Output is correct
7 Correct 60 ms 120844 KB Output is correct
8 Correct 62 ms 120728 KB Output is correct
9 Correct 60 ms 120776 KB Output is correct
10 Correct 62 ms 120840 KB Output is correct
11 Correct 63 ms 120764 KB Output is correct
12 Correct 57 ms 120628 KB Output is correct
13 Correct 70 ms 120752 KB Output is correct
14 Correct 61 ms 120480 KB Output is correct
15 Correct 62 ms 120536 KB Output is correct
16 Correct 60 ms 120872 KB Output is correct
17 Correct 59 ms 120748 KB Output is correct
18 Correct 61 ms 120796 KB Output is correct
19 Correct 71 ms 120500 KB Output is correct
20 Correct 63 ms 120780 KB Output is correct
21 Correct 60 ms 120836 KB Output is correct
22 Correct 59 ms 120860 KB Output is correct
23 Correct 64 ms 120472 KB Output is correct
24 Correct 58 ms 120652 KB Output is correct
25 Correct 64 ms 120876 KB Output is correct
26 Correct 61 ms 120796 KB Output is correct
27 Correct 59 ms 120712 KB Output is correct
28 Correct 57 ms 120580 KB Output is correct
29 Correct 61 ms 121236 KB Output is correct
30 Correct 60 ms 120908 KB Output is correct
31 Correct 73 ms 121252 KB Output is correct
32 Correct 64 ms 121120 KB Output is correct
33 Correct 91 ms 120800 KB Output is correct
34 Correct 62 ms 120824 KB Output is correct
35 Correct 69 ms 121196 KB Output is correct
36 Correct 61 ms 120720 KB Output is correct
37 Correct 62 ms 120796 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 120556 KB Output is correct
2 Correct 65 ms 120476 KB Output is correct
3 Correct 67 ms 120860 KB Output is correct
4 Correct 64 ms 120728 KB Output is correct
5 Correct 58 ms 120780 KB Output is correct
6 Correct 68 ms 120824 KB Output is correct
7 Correct 60 ms 120844 KB Output is correct
8 Correct 62 ms 120728 KB Output is correct
9 Correct 60 ms 120776 KB Output is correct
10 Correct 62 ms 120840 KB Output is correct
11 Correct 63 ms 120764 KB Output is correct
12 Correct 57 ms 120628 KB Output is correct
13 Correct 70 ms 120752 KB Output is correct
14 Correct 61 ms 120480 KB Output is correct
15 Correct 62 ms 120536 KB Output is correct
16 Correct 60 ms 120872 KB Output is correct
17 Correct 59 ms 120748 KB Output is correct
18 Correct 61 ms 120796 KB Output is correct
19 Correct 71 ms 120500 KB Output is correct
20 Correct 63 ms 120780 KB Output is correct
21 Correct 60 ms 120836 KB Output is correct
22 Correct 59 ms 120860 KB Output is correct
23 Correct 64 ms 120472 KB Output is correct
24 Correct 58 ms 120652 KB Output is correct
25 Correct 64 ms 120876 KB Output is correct
26 Correct 61 ms 120796 KB Output is correct
27 Correct 59 ms 120712 KB Output is correct
28 Correct 57 ms 120580 KB Output is correct
29 Correct 61 ms 121236 KB Output is correct
30 Correct 60 ms 120908 KB Output is correct
31 Correct 73 ms 121252 KB Output is correct
32 Correct 64 ms 121120 KB Output is correct
33 Correct 91 ms 120800 KB Output is correct
34 Correct 62 ms 120824 KB Output is correct
35 Correct 69 ms 121196 KB Output is correct
36 Correct 61 ms 120720 KB Output is correct
37 Correct 62 ms 120796 KB Output is correct
38 Correct 590 ms 180264 KB Output is correct
39 Runtime error 2404 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 70 ms 120572 KB Output is correct
2 Correct 66 ms 120504 KB Output is correct
3 Correct 63 ms 120456 KB Output is correct
4 Correct 60 ms 120468 KB Output is correct
5 Correct 67 ms 120596 KB Output is correct
6 Correct 60 ms 120616 KB Output is correct
7 Correct 60 ms 120740 KB Output is correct
8 Correct 63 ms 120464 KB Output is correct
9 Correct 62 ms 120528 KB Output is correct
10 Correct 62 ms 120640 KB Output is correct
11 Correct 59 ms 120576 KB Output is correct
12 Correct 61 ms 120832 KB Output is correct
13 Correct 95 ms 120932 KB Output is correct
14 Correct 133 ms 120680 KB Output is correct
15 Correct 98 ms 120796 KB Output is correct
16 Correct 290 ms 215036 KB Output is correct
17 Correct 518 ms 237000 KB Output is correct
18 Correct 802 ms 272104 KB Output is correct
19 Correct 347 ms 219908 KB Output is correct
20 Correct 338 ms 218956 KB Output is correct
21 Correct 390 ms 219340 KB Output is correct
22 Correct 484 ms 236212 KB Output is correct
23 Correct 382 ms 234892 KB Output is correct
24 Correct 402 ms 236776 KB Output is correct
25 Correct 401 ms 238128 KB Output is correct
26 Correct 390 ms 237680 KB Output is correct
27 Correct 405 ms 205988 KB Output is correct
28 Correct 401 ms 214480 KB Output is correct
29 Correct 386 ms 208536 KB Output is correct
30 Correct 370 ms 202148 KB Output is correct
31 Correct 323 ms 203136 KB Output is correct
32 Correct 317 ms 200280 KB Output is correct
33 Correct 294 ms 203144 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 120532 KB Output is correct
2 Correct 56 ms 120576 KB Output is correct
3 Correct 59 ms 120540 KB Output is correct
4 Correct 86 ms 120700 KB Output is correct
5 Correct 118 ms 120592 KB Output is correct
6 Correct 59 ms 120976 KB Output is correct
7 Correct 60 ms 120780 KB Output is correct
8 Correct 64 ms 121212 KB Output is correct
9 Correct 564 ms 180484 KB Output is correct
10 Runtime error 2391 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -