답안 #552159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
552159	2022-04-22T14:22:29 Z	errorgorn	Jail (JOI22_jail)	C++17	60 / 100	2232 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[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

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	120524 KB	Output is correct
2	Correct	59 ms	120620 KB	Output is correct
3	Correct	59 ms	120468 KB	Output is correct
4	Correct	66 ms	120624 KB	Output is correct
5	Correct	79 ms	120652 KB	Output is correct
6	Correct	73 ms	120700 KB	Output is correct
7	Correct	70 ms	120740 KB	Output is correct
8	Correct	70 ms	121040 KB	Output is correct
9	Correct	280 ms	175672 KB	Output is correct
10	Runtime error	2232 ms	1048576 KB	Execution killed with signal 9
11	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	63 ms	120524 KB	Output is correct
2	Correct	72 ms	120664 KB	Output is correct
3	Correct	59 ms	120732 KB	Output is correct
4	Correct	59 ms	120668 KB	Output is correct
5	Correct	62 ms	120652 KB	Output is correct
6	Correct	61 ms	120636 KB	Output is correct
7	Correct	61 ms	120720 KB	Output is correct
8	Correct	58 ms	120592 KB	Output is correct
9	Correct	69 ms	120624 KB	Output is correct
10	Correct	60 ms	120652 KB	Output is correct
11	Correct	59 ms	120608 KB	Output is correct
12	Correct	67 ms	120692 KB	Output is correct
13	Correct	64 ms	120648 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	63 ms	120524 KB	Output is correct
2	Correct	72 ms	120664 KB	Output is correct
3	Correct	59 ms	120732 KB	Output is correct
4	Correct	59 ms	120668 KB	Output is correct
5	Correct	62 ms	120652 KB	Output is correct
6	Correct	61 ms	120636 KB	Output is correct
7	Correct	61 ms	120720 KB	Output is correct
8	Correct	58 ms	120592 KB	Output is correct
9	Correct	69 ms	120624 KB	Output is correct
10	Correct	60 ms	120652 KB	Output is correct
11	Correct	59 ms	120608 KB	Output is correct
12	Correct	67 ms	120692 KB	Output is correct
13	Correct	64 ms	120648 KB	Output is correct
14	Correct	68 ms	120564 KB	Output is correct
15	Correct	61 ms	120536 KB	Output is correct
16	Correct	69 ms	120872 KB	Output is correct
17	Correct	61 ms	120648 KB	Output is correct
18	Correct	62 ms	120652 KB	Output is correct
19	Correct	58 ms	120528 KB	Output is correct
20	Correct	59 ms	120652 KB	Output is correct
21	Correct	66 ms	120704 KB	Output is correct
22	Correct	64 ms	120660 KB	Output is correct
23	Correct	60 ms	120540 KB	Output is correct
24	Correct	63 ms	120556 KB	Output is correct
25	Correct	59 ms	120684 KB	Output is correct
26	Correct	59 ms	120588 KB	Output is correct
27	Correct	61 ms	120716 KB	Output is correct
28	Correct	62 ms	120524 KB	Output is correct

Subtask #4
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	63 ms	120524 KB	Output is correct
2	Correct	72 ms	120664 KB	Output is correct
3	Correct	59 ms	120732 KB	Output is correct
4	Correct	59 ms	120668 KB	Output is correct
5	Correct	62 ms	120652 KB	Output is correct
6	Correct	61 ms	120636 KB	Output is correct
7	Correct	61 ms	120720 KB	Output is correct
8	Correct	58 ms	120592 KB	Output is correct
9	Correct	69 ms	120624 KB	Output is correct
10	Correct	60 ms	120652 KB	Output is correct
11	Correct	59 ms	120608 KB	Output is correct
12	Correct	67 ms	120692 KB	Output is correct
13	Correct	64 ms	120648 KB	Output is correct
14	Correct	68 ms	120564 KB	Output is correct
15	Correct	61 ms	120536 KB	Output is correct
16	Correct	69 ms	120872 KB	Output is correct
17	Correct	61 ms	120648 KB	Output is correct
18	Correct	62 ms	120652 KB	Output is correct
19	Correct	58 ms	120528 KB	Output is correct
20	Correct	59 ms	120652 KB	Output is correct
21	Correct	66 ms	120704 KB	Output is correct
22	Correct	64 ms	120660 KB	Output is correct
23	Correct	60 ms	120540 KB	Output is correct
24	Correct	63 ms	120556 KB	Output is correct
25	Correct	59 ms	120684 KB	Output is correct
26	Correct	59 ms	120588 KB	Output is correct
27	Correct	61 ms	120716 KB	Output is correct
28	Correct	62 ms	120524 KB	Output is correct
29	Correct	65 ms	121116 KB	Output is correct
30	Correct	88 ms	120740 KB	Output is correct
31	Correct	64 ms	120908 KB	Output is correct
32	Correct	76 ms	120716 KB	Output is correct
33	Correct	59 ms	120712 KB	Output is correct
34	Correct	66 ms	120800 KB	Output is correct
35	Correct	60 ms	120788 KB	Output is correct
36	Correct	58 ms	120652 KB	Output is correct
37	Correct	57 ms	120724 KB	Output is correct

Subtask #5
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	63 ms	120524 KB	Output is correct
2	Correct	72 ms	120664 KB	Output is correct
3	Correct	59 ms	120732 KB	Output is correct
4	Correct	59 ms	120668 KB	Output is correct
5	Correct	62 ms	120652 KB	Output is correct
6	Correct	61 ms	120636 KB	Output is correct
7	Correct	61 ms	120720 KB	Output is correct
8	Correct	58 ms	120592 KB	Output is correct
9	Correct	69 ms	120624 KB	Output is correct
10	Correct	60 ms	120652 KB	Output is correct
11	Correct	59 ms	120608 KB	Output is correct
12	Correct	67 ms	120692 KB	Output is correct
13	Correct	64 ms	120648 KB	Output is correct
14	Correct	68 ms	120564 KB	Output is correct
15	Correct	61 ms	120536 KB	Output is correct
16	Correct	69 ms	120872 KB	Output is correct
17	Correct	61 ms	120648 KB	Output is correct
18	Correct	62 ms	120652 KB	Output is correct
19	Correct	58 ms	120528 KB	Output is correct
20	Correct	59 ms	120652 KB	Output is correct
21	Correct	66 ms	120704 KB	Output is correct
22	Correct	64 ms	120660 KB	Output is correct
23	Correct	60 ms	120540 KB	Output is correct
24	Correct	63 ms	120556 KB	Output is correct
25	Correct	59 ms	120684 KB	Output is correct
26	Correct	59 ms	120588 KB	Output is correct
27	Correct	61 ms	120716 KB	Output is correct
28	Correct	62 ms	120524 KB	Output is correct
29	Correct	65 ms	121116 KB	Output is correct
30	Correct	88 ms	120740 KB	Output is correct
31	Correct	64 ms	120908 KB	Output is correct
32	Correct	76 ms	120716 KB	Output is correct
33	Correct	59 ms	120712 KB	Output is correct
34	Correct	66 ms	120800 KB	Output is correct
35	Correct	60 ms	120788 KB	Output is correct
36	Correct	58 ms	120652 KB	Output is correct
37	Correct	57 ms	120724 KB	Output is correct
38	Correct	277 ms	175564 KB	Output is correct
39	Runtime error	2090 ms	1048576 KB	Execution killed with signal 9
40	Halted	0 ms	0 KB	-

Subtask #6
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	120492 KB	Output is correct
2	Correct	56 ms	120560 KB	Output is correct
3	Correct	58 ms	120600 KB	Output is correct
4	Correct	59 ms	120572 KB	Output is correct
5	Correct	64 ms	120588 KB	Output is correct
6	Correct	60 ms	120700 KB	Output is correct
7	Correct	59 ms	120652 KB	Output is correct
8	Correct	57 ms	120524 KB	Output is correct
9	Correct	64 ms	120552 KB	Output is correct
10	Correct	57 ms	120648 KB	Output is correct
11	Correct	56 ms	120492 KB	Output is correct
12	Correct	60 ms	120748 KB	Output is correct
13	Correct	79 ms	120776 KB	Output is correct
14	Correct	90 ms	120620 KB	Output is correct
15	Correct	83 ms	120672 KB	Output is correct
16	Correct	174 ms	186288 KB	Output is correct
17	Correct	379 ms	208840 KB	Output is correct
18	Correct	618 ms	245440 KB	Output is correct
19	Correct	215 ms	191256 KB	Output is correct
20	Correct	218 ms	191664 KB	Output is correct
21	Correct	216 ms	191564 KB	Output is correct
22	Correct	340 ms	209532 KB	Output is correct
23	Correct	287 ms	208088 KB	Output is correct
24	Correct	264 ms	209904 KB	Output is correct
25	Correct	264 ms	210440 KB	Output is correct
26	Correct	265 ms	210224 KB	Output is correct
27	Correct	295 ms	199404 KB	Output is correct
28	Correct	301 ms	207980 KB	Output is correct
29	Correct	301 ms	201916 KB	Output is correct
30	Correct	254 ms	193216 KB	Output is correct
31	Correct	263 ms	194268 KB	Output is correct
32	Correct	240 ms	193336 KB	Output is correct
33	Correct	242 ms	196172 KB	Output is correct

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	120524 KB	Output is correct
2	Correct	59 ms	120620 KB	Output is correct
3	Correct	59 ms	120468 KB	Output is correct
4	Correct	66 ms	120624 KB	Output is correct
5	Correct	79 ms	120652 KB	Output is correct
6	Correct	73 ms	120700 KB	Output is correct
7	Correct	70 ms	120740 KB	Output is correct
8	Correct	70 ms	121040 KB	Output is correct
9	Correct	280 ms	175672 KB	Output is correct
10	Runtime error	2232 ms	1048576 KB	Execution killed with signal 9
11	Halted	0 ms	0 KB	-

답안 #552159

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