답안 #552157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
552157	2022-04-22T14:20:18 Z	errorgorn	Jail (JOI22_jail)	C++17	60 / 100	2274 ms	1048576 KB

jail

// 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[idx[curr][0].fi].pub(i);
					al2[i].pub(idx[curr][0].se);
					curr=tkd[curr][0];
				}
			}
			if (b!=g){
				int curr=tkd[b][0];
				while (curr!=g){
					al2[idx[curr][0].fi].pub(i);
					al2[i].pub(idx[curr][0].se);
					curr=tkd[curr][0];
				}
			}
			
			if (g!=a && g!=b){
				al2[idx[g][0].fi].pub(i);
				al2[i].pub(idx[g][0].se);
			}
		}
		
		// 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

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	120560 KB	Output is correct
2	Correct	58 ms	120572 KB	Output is correct
3	Correct	58 ms	120540 KB	Output is correct
4	Correct	69 ms	120780 KB	Output is correct
5	Correct	92 ms	120692 KB	Output is correct
6	Correct	61 ms	120676 KB	Output is correct
7	Correct	59 ms	120692 KB	Output is correct
8	Correct	58 ms	121116 KB	Output is correct
9	Correct	307 ms	175692 KB	Output is correct
10	Runtime error	2266 ms	1048576 KB	Execution killed with signal 9
11	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	120492 KB	Output is correct
2	Correct	64 ms	120528 KB	Output is correct
3	Correct	68 ms	120708 KB	Output is correct
4	Correct	58 ms	120616 KB	Output is correct
5	Correct	60 ms	120636 KB	Output is correct
6	Correct	59 ms	120652 KB	Output is correct
7	Correct	60 ms	120672 KB	Output is correct
8	Correct	67 ms	120780 KB	Output is correct
9	Correct	59 ms	120732 KB	Output is correct
10	Correct	58 ms	120652 KB	Output is correct
11	Correct	60 ms	120736 KB	Output is correct
12	Correct	75 ms	120712 KB	Output is correct
13	Correct	58 ms	120700 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	120492 KB	Output is correct
2	Correct	64 ms	120528 KB	Output is correct
3	Correct	68 ms	120708 KB	Output is correct
4	Correct	58 ms	120616 KB	Output is correct
5	Correct	60 ms	120636 KB	Output is correct
6	Correct	59 ms	120652 KB	Output is correct
7	Correct	60 ms	120672 KB	Output is correct
8	Correct	67 ms	120780 KB	Output is correct
9	Correct	59 ms	120732 KB	Output is correct
10	Correct	58 ms	120652 KB	Output is correct
11	Correct	60 ms	120736 KB	Output is correct
12	Correct	75 ms	120712 KB	Output is correct
13	Correct	58 ms	120700 KB	Output is correct
14	Correct	57 ms	120524 KB	Output is correct
15	Correct	60 ms	120544 KB	Output is correct
16	Correct	62 ms	120748 KB	Output is correct
17	Correct	69 ms	120636 KB	Output is correct
18	Correct	59 ms	120732 KB	Output is correct
19	Correct	57 ms	120508 KB	Output is correct
20	Correct	59 ms	120696 KB	Output is correct
21	Correct	63 ms	120652 KB	Output is correct
22	Correct	64 ms	120772 KB	Output is correct
23	Correct	58 ms	120472 KB	Output is correct
24	Correct	59 ms	120524 KB	Output is correct
25	Correct	58 ms	120732 KB	Output is correct
26	Correct	59 ms	120620 KB	Output is correct
27	Correct	62 ms	120756 KB	Output is correct
28	Correct	70 ms	120460 KB	Output is correct

Subtask #4
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	120492 KB	Output is correct
2	Correct	64 ms	120528 KB	Output is correct
3	Correct	68 ms	120708 KB	Output is correct
4	Correct	58 ms	120616 KB	Output is correct
5	Correct	60 ms	120636 KB	Output is correct
6	Correct	59 ms	120652 KB	Output is correct
7	Correct	60 ms	120672 KB	Output is correct
8	Correct	67 ms	120780 KB	Output is correct
9	Correct	59 ms	120732 KB	Output is correct
10	Correct	58 ms	120652 KB	Output is correct
11	Correct	60 ms	120736 KB	Output is correct
12	Correct	75 ms	120712 KB	Output is correct
13	Correct	58 ms	120700 KB	Output is correct
14	Correct	57 ms	120524 KB	Output is correct
15	Correct	60 ms	120544 KB	Output is correct
16	Correct	62 ms	120748 KB	Output is correct
17	Correct	69 ms	120636 KB	Output is correct
18	Correct	59 ms	120732 KB	Output is correct
19	Correct	57 ms	120508 KB	Output is correct
20	Correct	59 ms	120696 KB	Output is correct
21	Correct	63 ms	120652 KB	Output is correct
22	Correct	64 ms	120772 KB	Output is correct
23	Correct	58 ms	120472 KB	Output is correct
24	Correct	59 ms	120524 KB	Output is correct
25	Correct	58 ms	120732 KB	Output is correct
26	Correct	59 ms	120620 KB	Output is correct
27	Correct	62 ms	120756 KB	Output is correct
28	Correct	70 ms	120460 KB	Output is correct
29	Correct	67 ms	121128 KB	Output is correct
30	Correct	58 ms	120784 KB	Output is correct
31	Correct	62 ms	120892 KB	Output is correct
32	Correct	60 ms	120692 KB	Output is correct
33	Correct	60 ms	120640 KB	Output is correct
34	Correct	72 ms	120688 KB	Output is correct
35	Correct	66 ms	120952 KB	Output is correct
36	Correct	62 ms	120692 KB	Output is correct
37	Correct	58 ms	120776 KB	Output is correct

Subtask #5
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	120492 KB	Output is correct
2	Correct	64 ms	120528 KB	Output is correct
3	Correct	68 ms	120708 KB	Output is correct
4	Correct	58 ms	120616 KB	Output is correct
5	Correct	60 ms	120636 KB	Output is correct
6	Correct	59 ms	120652 KB	Output is correct
7	Correct	60 ms	120672 KB	Output is correct
8	Correct	67 ms	120780 KB	Output is correct
9	Correct	59 ms	120732 KB	Output is correct
10	Correct	58 ms	120652 KB	Output is correct
11	Correct	60 ms	120736 KB	Output is correct
12	Correct	75 ms	120712 KB	Output is correct
13	Correct	58 ms	120700 KB	Output is correct
14	Correct	57 ms	120524 KB	Output is correct
15	Correct	60 ms	120544 KB	Output is correct
16	Correct	62 ms	120748 KB	Output is correct
17	Correct	69 ms	120636 KB	Output is correct
18	Correct	59 ms	120732 KB	Output is correct
19	Correct	57 ms	120508 KB	Output is correct
20	Correct	59 ms	120696 KB	Output is correct
21	Correct	63 ms	120652 KB	Output is correct
22	Correct	64 ms	120772 KB	Output is correct
23	Correct	58 ms	120472 KB	Output is correct
24	Correct	59 ms	120524 KB	Output is correct
25	Correct	58 ms	120732 KB	Output is correct
26	Correct	59 ms	120620 KB	Output is correct
27	Correct	62 ms	120756 KB	Output is correct
28	Correct	70 ms	120460 KB	Output is correct
29	Correct	67 ms	121128 KB	Output is correct
30	Correct	58 ms	120784 KB	Output is correct
31	Correct	62 ms	120892 KB	Output is correct
32	Correct	60 ms	120692 KB	Output is correct
33	Correct	60 ms	120640 KB	Output is correct
34	Correct	72 ms	120688 KB	Output is correct
35	Correct	66 ms	120952 KB	Output is correct
36	Correct	62 ms	120692 KB	Output is correct
37	Correct	58 ms	120776 KB	Output is correct
38	Correct	328 ms	175476 KB	Output is correct
39	Runtime error	2274 ms	1048576 KB	Execution killed with signal 9
40	Halted	0 ms	0 KB	-

Subtask #6
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	120448 KB	Output is correct
2	Correct	60 ms	120568 KB	Output is correct
3	Correct	60 ms	120524 KB	Output is correct
4	Correct	60 ms	120460 KB	Output is correct
5	Correct	64 ms	120600 KB	Output is correct
6	Correct	62 ms	120704 KB	Output is correct
7	Correct	71 ms	120652 KB	Output is correct
8	Correct	66 ms	120520 KB	Output is correct
9	Correct	57 ms	120528 KB	Output is correct
10	Correct	65 ms	120576 KB	Output is correct
11	Correct	61 ms	120572 KB	Output is correct
12	Correct	60 ms	120692 KB	Output is correct
13	Correct	96 ms	120908 KB	Output is correct
14	Correct	93 ms	120800 KB	Output is correct
15	Correct	103 ms	120756 KB	Output is correct
16	Correct	197 ms	186580 KB	Output is correct
17	Correct	387 ms	209268 KB	Output is correct
18	Correct	678 ms	244544 KB	Output is correct
19	Correct	248 ms	191512 KB	Output is correct
20	Correct	224 ms	191516 KB	Output is correct
21	Correct	239 ms	191676 KB	Output is correct
22	Correct	363 ms	209596 KB	Output is correct
23	Correct	265 ms	208304 KB	Output is correct
24	Correct	302 ms	209824 KB	Output is correct
25	Correct	281 ms	210516 KB	Output is correct
26	Correct	305 ms	210524 KB	Output is correct
27	Correct	323 ms	199804 KB	Output is correct
28	Correct	335 ms	208264 KB	Output is correct
29	Correct	328 ms	202212 KB	Output is correct
30	Correct	278 ms	193472 KB	Output is correct
31	Correct	262 ms	194536 KB	Output is correct
32	Correct	240 ms	193484 KB	Output is correct
33	Correct	281 ms	196456 KB	Output is correct

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	120560 KB	Output is correct
2	Correct	58 ms	120572 KB	Output is correct
3	Correct	58 ms	120540 KB	Output is correct
4	Correct	69 ms	120780 KB	Output is correct
5	Correct	92 ms	120692 KB	Output is correct
6	Correct	61 ms	120676 KB	Output is correct
7	Correct	59 ms	120692 KB	Output is correct
8	Correct	58 ms	121116 KB	Output is correct
9	Correct	307 ms	175692 KB	Output is correct
10	Runtime error	2266 ms	1048576 KB	Execution killed with signal 9
11	Halted	0 ms	0 KB	-

답안 #552157

Compilation message

Subtask #1 0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 16.0 / 16.0

Subtask #4 28.0 / 28.0

Subtask #5 0 / 12.0

Subtask #6 11.0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
16.0 / 16.0

Subtask #4
28.0 / 28.0

Subtask #5
0 / 12.0

Subtask #6
11.0 / 11.0

Subtask #7
0 / 23.0