oj.uz

Submission #552152

# Submission time Handle Problem Language Result Execution time Memory
552152 2022-04-22T14:11:32 Z errorgorn Jail (JOI22_jail) C++17
60 / 100
 2495 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 57 ms 120484 KB Output is correct
2 Correct 55 ms 120524 KB Output is correct
3 Correct 56 ms 120476 KB Output is correct
4 Correct 68 ms 120800 KB Output is correct
5 Correct 82 ms 120528 KB Output is correct
6 Correct 59 ms 120644 KB Output is correct
7 Correct 58 ms 120668 KB Output is correct
8 Correct 66 ms 121112 KB Output is correct
9 Correct 346 ms 175692 KB Output is correct
10 Runtime error 2495 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 65 ms 120464 KB Output is correct
2 Correct 72 ms 120516 KB Output is correct
3 Correct 84 ms 120748 KB Output is correct
4 Correct 75 ms 120644 KB Output is correct
5 Correct 66 ms 120676 KB Output is correct
6 Correct 68 ms 120748 KB Output is correct
7 Correct 71 ms 120652 KB Output is correct
8 Correct 66 ms 120788 KB Output is correct
9 Correct 78 ms 120728 KB Output is correct
10 Correct 65 ms 120736 KB Output is correct
11 Correct 65 ms 120736 KB Output is correct
12 Correct 67 ms 120676 KB Output is correct
13 Correct 65 ms 120688 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 120464 KB Output is correct
2 Correct 72 ms 120516 KB Output is correct
3 Correct 84 ms 120748 KB Output is correct
4 Correct 75 ms 120644 KB Output is correct
5 Correct 66 ms 120676 KB Output is correct
6 Correct 68 ms 120748 KB Output is correct
7 Correct 71 ms 120652 KB Output is correct
8 Correct 66 ms 120788 KB Output is correct
9 Correct 78 ms 120728 KB Output is correct
10 Correct 65 ms 120736 KB Output is correct
11 Correct 65 ms 120736 KB Output is correct
12 Correct 67 ms 120676 KB Output is correct
13 Correct 65 ms 120688 KB Output is correct
14 Correct 76 ms 120544 KB Output is correct
15 Correct 65 ms 120556 KB Output is correct
16 Correct 67 ms 120700 KB Output is correct
17 Correct 66 ms 120736 KB Output is correct
18 Correct 65 ms 120768 KB Output is correct
19 Correct 67 ms 120520 KB Output is correct
20 Correct 69 ms 120720 KB Output is correct
21 Correct 71 ms 120652 KB Output is correct
22 Correct 66 ms 120764 KB Output is correct
23 Correct 64 ms 120528 KB Output is correct
24 Correct 66 ms 120524 KB Output is correct
25 Correct 69 ms 120780 KB Output is correct
26 Correct 67 ms 120664 KB Output is correct
27 Correct 78 ms 120636 KB Output is correct
28 Correct 63 ms 120524 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 120464 KB Output is correct
2 Correct 72 ms 120516 KB Output is correct
3 Correct 84 ms 120748 KB Output is correct
4 Correct 75 ms 120644 KB Output is correct
5 Correct 66 ms 120676 KB Output is correct
6 Correct 68 ms 120748 KB Output is correct
7 Correct 71 ms 120652 KB Output is correct
8 Correct 66 ms 120788 KB Output is correct
9 Correct 78 ms 120728 KB Output is correct
10 Correct 65 ms 120736 KB Output is correct
11 Correct 65 ms 120736 KB Output is correct
12 Correct 67 ms 120676 KB Output is correct
13 Correct 65 ms 120688 KB Output is correct
14 Correct 76 ms 120544 KB Output is correct
15 Correct 65 ms 120556 KB Output is correct
16 Correct 67 ms 120700 KB Output is correct
17 Correct 66 ms 120736 KB Output is correct
18 Correct 65 ms 120768 KB Output is correct
19 Correct 67 ms 120520 KB Output is correct
20 Correct 69 ms 120720 KB Output is correct
21 Correct 71 ms 120652 KB Output is correct
22 Correct 66 ms 120764 KB Output is correct
23 Correct 64 ms 120528 KB Output is correct
24 Correct 66 ms 120524 KB Output is correct
25 Correct 69 ms 120780 KB Output is correct
26 Correct 67 ms 120664 KB Output is correct
27 Correct 78 ms 120636 KB Output is correct
28 Correct 63 ms 120524 KB Output is correct
29 Correct 68 ms 121184 KB Output is correct
30 Correct 68 ms 120840 KB Output is correct
31 Correct 80 ms 120940 KB Output is correct
32 Correct 69 ms 120744 KB Output is correct
33 Correct 68 ms 120724 KB Output is correct
34 Correct 71 ms 120744 KB Output is correct
35 Correct 79 ms 120904 KB Output is correct
36 Correct 67 ms 120760 KB Output is correct
37 Correct 69 ms 120752 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 120464 KB Output is correct
2 Correct 72 ms 120516 KB Output is correct
3 Correct 84 ms 120748 KB Output is correct
4 Correct 75 ms 120644 KB Output is correct
5 Correct 66 ms 120676 KB Output is correct
6 Correct 68 ms 120748 KB Output is correct
7 Correct 71 ms 120652 KB Output is correct
8 Correct 66 ms 120788 KB Output is correct
9 Correct 78 ms 120728 KB Output is correct
10 Correct 65 ms 120736 KB Output is correct
11 Correct 65 ms 120736 KB Output is correct
12 Correct 67 ms 120676 KB Output is correct
13 Correct 65 ms 120688 KB Output is correct
14 Correct 76 ms 120544 KB Output is correct
15 Correct 65 ms 120556 KB Output is correct
16 Correct 67 ms 120700 KB Output is correct
17 Correct 66 ms 120736 KB Output is correct
18 Correct 65 ms 120768 KB Output is correct
19 Correct 67 ms 120520 KB Output is correct
20 Correct 69 ms 120720 KB Output is correct
21 Correct 71 ms 120652 KB Output is correct
22 Correct 66 ms 120764 KB Output is correct
23 Correct 64 ms 120528 KB Output is correct
24 Correct 66 ms 120524 KB Output is correct
25 Correct 69 ms 120780 KB Output is correct
26 Correct 67 ms 120664 KB Output is correct
27 Correct 78 ms 120636 KB Output is correct
28 Correct 63 ms 120524 KB Output is correct
29 Correct 68 ms 121184 KB Output is correct
30 Correct 68 ms 120840 KB Output is correct
31 Correct 80 ms 120940 KB Output is correct
32 Correct 69 ms 120744 KB Output is correct
33 Correct 68 ms 120724 KB Output is correct
34 Correct 71 ms 120744 KB Output is correct
35 Correct 79 ms 120904 KB Output is correct
36 Correct 67 ms 120760 KB Output is correct
37 Correct 69 ms 120752 KB Output is correct
38 Correct 355 ms 176332 KB Output is correct
39 Runtime error 2267 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 67 ms 120488 KB Output is correct
2 Correct 65 ms 120676 KB Output is correct
3 Correct 64 ms 120472 KB Output is correct
4 Correct 64 ms 120572 KB Output is correct
5 Correct 82 ms 120692 KB Output is correct
6 Correct 75 ms 120680 KB Output is correct
7 Correct 63 ms 120656 KB Output is correct
8 Correct 63 ms 120524 KB Output is correct
9 Correct 70 ms 120536 KB Output is correct
10 Correct 69 ms 120540 KB Output is correct
11 Correct 71 ms 120600 KB Output is correct
12 Correct 67 ms 120752 KB Output is correct
13 Correct 93 ms 121208 KB Output is correct
14 Correct 98 ms 121380 KB Output is correct
15 Correct 94 ms 121276 KB Output is correct
16 Correct 205 ms 187268 KB Output is correct
17 Correct 395 ms 209116 KB Output is correct
18 Correct 681 ms 247596 KB Output is correct
19 Correct 223 ms 192020 KB Output is correct
20 Correct 258 ms 191568 KB Output is correct
21 Correct 243 ms 191656 KB Output is correct
22 Correct 365 ms 211180 KB Output is correct
23 Correct 311 ms 209648 KB Output is correct
24 Correct 274 ms 209852 KB Output is correct
25 Correct 280 ms 210532 KB Output is correct
26 Correct 317 ms 212012 KB Output is correct
27 Correct 318 ms 200212 KB Output is correct
28 Correct 343 ms 209172 KB Output is correct
29 Correct 344 ms 204444 KB Output is correct
30 Correct 268 ms 195308 KB Output is correct
31 Correct 302 ms 195712 KB Output is correct
32 Correct 250 ms 195488 KB Output is correct
33 Correct 252 ms 197376 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 120484 KB Output is correct
2 Correct 55 ms 120524 KB Output is correct
3 Correct 56 ms 120476 KB Output is correct
4 Correct 68 ms 120800 KB Output is correct
5 Correct 82 ms 120528 KB Output is correct
6 Correct 59 ms 120644 KB Output is correct
7 Correct 58 ms 120668 KB Output is correct
8 Correct 66 ms 121112 KB Output is correct
9 Correct 346 ms 175692 KB Output is correct
10 Runtime error 2495 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -