oj.uz

Submission #552160

# Submission time Handle Problem Language Result Execution time Memory
552160 2022-04-22T14:24:44 Z errorgorn Jail (JOI22_jail) C++17
60 / 100
 2644 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 58 ms 120524 KB Output is correct
2 Correct 57 ms 120452 KB Output is correct
3 Correct 58 ms 120568 KB Output is correct
4 Correct 71 ms 120564 KB Output is correct
5 Correct 109 ms 120668 KB Output is correct
6 Correct 62 ms 120844 KB Output is correct
7 Correct 60 ms 120788 KB Output is correct
8 Correct 59 ms 121136 KB Output is correct
9 Correct 349 ms 176668 KB Output is correct
10 Runtime error 2644 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 60 ms 120600 KB Output is correct
2 Correct 66 ms 120512 KB Output is correct
3 Correct 61 ms 120700 KB Output is correct
4 Correct 66 ms 120824 KB Output is correct
5 Correct 59 ms 120716 KB Output is correct
6 Correct 67 ms 120760 KB Output is correct
7 Correct 60 ms 120652 KB Output is correct
8 Correct 62 ms 120608 KB Output is correct
9 Correct 58 ms 120652 KB Output is correct
10 Correct 59 ms 120684 KB Output is correct
11 Correct 59 ms 120712 KB Output is correct
12 Correct 62 ms 120700 KB Output is correct
13 Correct 58 ms 120664 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 120600 KB Output is correct
2 Correct 66 ms 120512 KB Output is correct
3 Correct 61 ms 120700 KB Output is correct
4 Correct 66 ms 120824 KB Output is correct
5 Correct 59 ms 120716 KB Output is correct
6 Correct 67 ms 120760 KB Output is correct
7 Correct 60 ms 120652 KB Output is correct
8 Correct 62 ms 120608 KB Output is correct
9 Correct 58 ms 120652 KB Output is correct
10 Correct 59 ms 120684 KB Output is correct
11 Correct 59 ms 120712 KB Output is correct
12 Correct 62 ms 120700 KB Output is correct
13 Correct 58 ms 120664 KB Output is correct
14 Correct 57 ms 120568 KB Output is correct
15 Correct 56 ms 120520 KB Output is correct
16 Correct 59 ms 120788 KB Output is correct
17 Correct 61 ms 120672 KB Output is correct
18 Correct 67 ms 120868 KB Output is correct
19 Correct 59 ms 120560 KB Output is correct
20 Correct 61 ms 120688 KB Output is correct
21 Correct 60 ms 120656 KB Output is correct
22 Correct 58 ms 120724 KB Output is correct
23 Correct 57 ms 120516 KB Output is correct
24 Correct 65 ms 120648 KB Output is correct
25 Correct 63 ms 120768 KB Output is correct
26 Correct 70 ms 120660 KB Output is correct
27 Correct 59 ms 120620 KB Output is correct
28 Correct 62 ms 120584 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 120600 KB Output is correct
2 Correct 66 ms 120512 KB Output is correct
3 Correct 61 ms 120700 KB Output is correct
4 Correct 66 ms 120824 KB Output is correct
5 Correct 59 ms 120716 KB Output is correct
6 Correct 67 ms 120760 KB Output is correct
7 Correct 60 ms 120652 KB Output is correct
8 Correct 62 ms 120608 KB Output is correct
9 Correct 58 ms 120652 KB Output is correct
10 Correct 59 ms 120684 KB Output is correct
11 Correct 59 ms 120712 KB Output is correct
12 Correct 62 ms 120700 KB Output is correct
13 Correct 58 ms 120664 KB Output is correct
14 Correct 57 ms 120568 KB Output is correct
15 Correct 56 ms 120520 KB Output is correct
16 Correct 59 ms 120788 KB Output is correct
17 Correct 61 ms 120672 KB Output is correct
18 Correct 67 ms 120868 KB Output is correct
19 Correct 59 ms 120560 KB Output is correct
20 Correct 61 ms 120688 KB Output is correct
21 Correct 60 ms 120656 KB Output is correct
22 Correct 58 ms 120724 KB Output is correct
23 Correct 57 ms 120516 KB Output is correct
24 Correct 65 ms 120648 KB Output is correct
25 Correct 63 ms 120768 KB Output is correct
26 Correct 70 ms 120660 KB Output is correct
27 Correct 59 ms 120620 KB Output is correct
28 Correct 62 ms 120584 KB Output is correct
29 Correct 65 ms 121124 KB Output is correct
30 Correct 61 ms 120732 KB Output is correct
31 Correct 62 ms 121200 KB Output is correct
32 Correct 61 ms 120908 KB Output is correct
33 Correct 65 ms 120632 KB Output is correct
34 Correct 62 ms 120704 KB Output is correct
35 Correct 61 ms 121236 KB Output is correct
36 Correct 70 ms 120652 KB Output is correct
37 Correct 69 ms 120716 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 120600 KB Output is correct
2 Correct 66 ms 120512 KB Output is correct
3 Correct 61 ms 120700 KB Output is correct
4 Correct 66 ms 120824 KB Output is correct
5 Correct 59 ms 120716 KB Output is correct
6 Correct 67 ms 120760 KB Output is correct
7 Correct 60 ms 120652 KB Output is correct
8 Correct 62 ms 120608 KB Output is correct
9 Correct 58 ms 120652 KB Output is correct
10 Correct 59 ms 120684 KB Output is correct
11 Correct 59 ms 120712 KB Output is correct
12 Correct 62 ms 120700 KB Output is correct
13 Correct 58 ms 120664 KB Output is correct
14 Correct 57 ms 120568 KB Output is correct
15 Correct 56 ms 120520 KB Output is correct
16 Correct 59 ms 120788 KB Output is correct
17 Correct 61 ms 120672 KB Output is correct
18 Correct 67 ms 120868 KB Output is correct
19 Correct 59 ms 120560 KB Output is correct
20 Correct 61 ms 120688 KB Output is correct
21 Correct 60 ms 120656 KB Output is correct
22 Correct 58 ms 120724 KB Output is correct
23 Correct 57 ms 120516 KB Output is correct
24 Correct 65 ms 120648 KB Output is correct
25 Correct 63 ms 120768 KB Output is correct
26 Correct 70 ms 120660 KB Output is correct
27 Correct 59 ms 120620 KB Output is correct
28 Correct 62 ms 120584 KB Output is correct
29 Correct 65 ms 121124 KB Output is correct
30 Correct 61 ms 120732 KB Output is correct
31 Correct 62 ms 121200 KB Output is correct
32 Correct 61 ms 120908 KB Output is correct
33 Correct 65 ms 120632 KB Output is correct
34 Correct 62 ms 120704 KB Output is correct
35 Correct 61 ms 121236 KB Output is correct
36 Correct 70 ms 120652 KB Output is correct
37 Correct 69 ms 120716 KB Output is correct
38 Correct 379 ms 176592 KB Output is correct
39 Runtime error 2549 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 57 ms 120460 KB Output is correct
2 Correct 68 ms 120568 KB Output is correct
3 Correct 61 ms 120532 KB Output is correct
4 Correct 57 ms 120532 KB Output is correct
5 Correct 64 ms 120588 KB Output is correct
6 Correct 57 ms 120688 KB Output is correct
7 Correct 59 ms 120600 KB Output is correct
8 Correct 58 ms 120536 KB Output is correct
9 Correct 65 ms 120468 KB Output is correct
10 Correct 67 ms 120608 KB Output is correct
11 Correct 59 ms 120504 KB Output is correct
12 Correct 58 ms 120660 KB Output is correct
13 Correct 88 ms 120848 KB Output is correct
14 Correct 94 ms 120744 KB Output is correct
15 Correct 114 ms 120760 KB Output is correct
16 Correct 213 ms 191692 KB Output is correct
17 Correct 392 ms 214000 KB Output is correct
18 Correct 720 ms 250712 KB Output is correct
19 Correct 263 ms 196476 KB Output is correct
20 Correct 248 ms 196760 KB Output is correct
21 Correct 256 ms 196728 KB Output is correct
22 Correct 409 ms 214508 KB Output is correct
23 Correct 292 ms 213164 KB Output is correct
24 Correct 303 ms 214836 KB Output is correct
25 Correct 416 ms 215724 KB Output is correct
26 Correct 307 ms 215404 KB Output is correct
27 Correct 324 ms 201416 KB Output is correct
28 Correct 334 ms 209688 KB Output is correct
29 Correct 323 ms 203800 KB Output is correct
30 Correct 286 ms 194992 KB Output is correct
31 Correct 284 ms 196248 KB Output is correct
32 Correct 282 ms 195188 KB Output is correct
33 Correct 275 ms 198052 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 120524 KB Output is correct
2 Correct 57 ms 120452 KB Output is correct
3 Correct 58 ms 120568 KB Output is correct
4 Correct 71 ms 120564 KB Output is correct
5 Correct 109 ms 120668 KB Output is correct
6 Correct 62 ms 120844 KB Output is correct
7 Correct 60 ms 120788 KB Output is correct
8 Correct 59 ms 121136 KB Output is correct
9 Correct 349 ms 176668 KB Output is correct
10 Runtime error 2644 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -