답안 #654915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654915	2022-11-02T00:41:01 Z	inksamurai	Village (BOI20_village)	C++17	50 / 100	131 ms	27616 KB

Village

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3fm6nhZ ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define all(a) a.begin(),a.end()

signed main(){
_3fm6nhZ;
	int n;
	cin>>n;
	vec(vi) adj(n);
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		u-=1,v-=1;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	int ans=0;
	vi ert(n);
	auto dfs=[&](auto self,int v,int par)->int{
		vi rbts;
		for(auto u:adj[v]){
			if(u==par) continue;
			int e=self(self,u,v);
			if(e) rbts.pb(u);
		}
		if(sz(rbts)==0) return 1;
		for(int i=0;i<sz(rbts)-sz(rbts)%2;i+=2){
			ert[rbts[i]]=rbts[i+1];
			ert[rbts[i+1]]=rbts[i];
			ans+=4;
		}
		if(sz(rbts)%2){
			ert[v]=rbts.back();
			ert[rbts.back()]=v;
			ans+=2;
		}else{
			ert[v]=rbts.back();
			ert[ert[rbts.back()]]=v;
		}
		return 0;
	};
	int e=dfs(dfs,0,-1);
	if(e){
		int v=0;
		int u=adj[0][0];
		ans+=2;
		rep(s,n){
			if(ert[s]==u){
				ert[v]=u;
				ert[s]=0;
				break;
			}
		}
	}
	int ans1=0;
	vi chs(n);
	auto pre_rfs=[&](auto self,int v,int par)->void{
		chs[v]=1;
		for(auto u:adj[v]){
			if(u==par) continue;
			self(self,u,v);
			chs[v]+=chs[u];
			ans1+=2*min(chs[u],n-chs[u]);
		}
	};
	pre_rfs(pre_rfs,0,-1);
	auto rfs=[&](auto self,int v,int par)->int{
		for(auto u:adj[v]){
			if(u==par) continue;
			if(2*chs[u]>=n){
				return self(self,u,v);
			}
		}
		return v;
	};
	int rt=rfs(rfs,0,-1);
	chs=vi(n,0);
	ans1=0;
	pre_rfs(pre_rfs,rt,-1);
	vi rbts;
	auto add=[&](auto self,int v,int par)->void{
		rbts.pb(v);
		for(auto u:adj[v]){
			if(u==par) continue;
			self(self,u,v);
		}
	};
	vi delay={rt};
	vi usd(n,0);
	vi ert1(n);
	auto ask=[&](auto self,int v,int par)->void{
		// print(v,sz(rbts)+sz(delay));
		assert(sz(rbts)+sz(delay));
		if(sz(delay)){
			int s=delay.back();
			ert1[s]=v;
			delay.pop_back();
		}else{
			int s=rbts.back();
			usd[s]=1;
			ert1[s]=v;
			rbts.pop_back();
		}
		for(auto u:adj[v]){
			if(u==par) continue;
			self(self,u,v);
		}
	};
	sort(all(adj[rt]),[&](int l,int r){
		return chs[l]<chs[r];
	});
	for(auto u:adj[rt]){
		add(add,u,rt);
	}
	per(i,sz(adj[rt])){
		int u=adj[rt][i];
		vi now;
		rep(_,chs[u]){
			if(!sz(rbts) or usd[rbts.back()]) continue;
			now.pb(rbts.back());
			rbts.pop_back();
		}
		ask(ask,u,rt);
		for(auto v:now){
			delay.pb(v);
		}
	}
	assert(sz(delay));
	ert1[delay.back()]=rt;
	cout<<ans<<" "<<ans1<<"\n";
	rep(i,n){
		cout<<ert[i]+1<<" ";
	}
	print();
	rep(i,n){
		cout<<ert1[i]+1<<" ";
	}
}

Subtask #1

6.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Partially correct	0 ms	212 KB	Partially correct
3	Correct	0 ms	212 KB	Output is correct
4	Partially correct	0 ms	212 KB	Partially correct
5	Correct	0 ms	212 KB	Output is correct
6	Partially correct	0 ms	212 KB	Partially correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Partially correct	1 ms	212 KB	Partially correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	284 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Partially correct	0 ms	212 KB	Partially correct

Subtask #2

19.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	1 ms	340 KB	Partially correct
2	Correct	1 ms	340 KB	Output is correct
3	Partially correct	1 ms	340 KB	Partially correct
4	Partially correct	1 ms	340 KB	Partially correct
5	Partially correct	1 ms	340 KB	Partially correct
6	Partially correct	1 ms	340 KB	Partially correct
7	Correct	1 ms	468 KB	Output is correct
8	Partially correct	1 ms	340 KB	Partially correct
9	Partially correct	1 ms	340 KB	Partially correct
10	Partially correct	1 ms	468 KB	Partially correct
11	Partially correct	1 ms	468 KB	Partially correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Partially correct	1 ms	340 KB	Partially correct
15	Partially correct	1 ms	340 KB	Partially correct
16	Correct	1 ms	340 KB	Output is correct
17	Partially correct	1 ms	340 KB	Partially correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Partially correct	1 ms	340 KB	Partially correct
22	Partially correct	1 ms	340 KB	Partially correct
23	Partially correct	1 ms	340 KB	Partially correct
24	Partially correct	1 ms	340 KB	Partially correct
25	Correct	1 ms	340 KB	Output is correct
26	Partially correct	1 ms	340 KB	Partially correct
27	Partially correct	1 ms	340 KB	Partially correct
28	Partially correct	1 ms	340 KB	Partially correct
29	Partially correct	1 ms	340 KB	Partially correct
30	Partially correct	1 ms	340 KB	Partially correct

Subtask #3

25.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Partially correct	0 ms	212 KB	Partially correct
3	Correct	0 ms	212 KB	Output is correct
4	Partially correct	0 ms	212 KB	Partially correct
5	Correct	0 ms	212 KB	Output is correct
6	Partially correct	0 ms	212 KB	Partially correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Partially correct	1 ms	212 KB	Partially correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	284 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Partially correct	0 ms	212 KB	Partially correct
18	Partially correct	1 ms	340 KB	Partially correct
19	Correct	1 ms	340 KB	Output is correct
20	Partially correct	1 ms	340 KB	Partially correct
21	Partially correct	1 ms	340 KB	Partially correct
22	Partially correct	1 ms	340 KB	Partially correct
23	Partially correct	1 ms	340 KB	Partially correct
24	Correct	1 ms	468 KB	Output is correct
25	Partially correct	1 ms	340 KB	Partially correct
26	Partially correct	1 ms	340 KB	Partially correct
27	Partially correct	1 ms	468 KB	Partially correct
28	Partially correct	1 ms	468 KB	Partially correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Partially correct	1 ms	340 KB	Partially correct
32	Partially correct	1 ms	340 KB	Partially correct
33	Correct	1 ms	340 KB	Output is correct
34	Partially correct	1 ms	340 KB	Partially correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Partially correct	1 ms	340 KB	Partially correct
39	Partially correct	1 ms	340 KB	Partially correct
40	Partially correct	1 ms	340 KB	Partially correct
41	Partially correct	1 ms	340 KB	Partially correct
42	Correct	1 ms	340 KB	Output is correct
43	Partially correct	1 ms	340 KB	Partially correct
44	Partially correct	1 ms	340 KB	Partially correct
45	Partially correct	1 ms	340 KB	Partially correct
46	Partially correct	1 ms	340 KB	Partially correct
47	Partially correct	1 ms	340 KB	Partially correct
48	Partially correct	104 ms	11792 KB	Partially correct
49	Correct	82 ms	12860 KB	Output is correct
50	Partially correct	90 ms	12872 KB	Partially correct
51	Partially correct	67 ms	9964 KB	Partially correct
52	Partially correct	82 ms	12320 KB	Partially correct
53	Partially correct	69 ms	11560 KB	Partially correct
54	Correct	47 ms	13304 KB	Output is correct
55	Correct	120 ms	27616 KB	Output is correct
56	Partially correct	122 ms	19988 KB	Partially correct
57	Partially correct	109 ms	17600 KB	Partially correct
58	Partially correct	113 ms	15280 KB	Partially correct
59	Partially correct	77 ms	13116 KB	Partially correct
60	Correct	62 ms	12656 KB	Output is correct
61	Partially correct	57 ms	12672 KB	Partially correct
62	Correct	61 ms	13272 KB	Output is correct
63	Partially correct	57 ms	12524 KB	Partially correct
64	Partially correct	66 ms	12940 KB	Partially correct
65	Correct	78 ms	13376 KB	Output is correct
66	Correct	57 ms	12144 KB	Output is correct
67	Partially correct	39 ms	9744 KB	Partially correct
68	Partially correct	83 ms	11236 KB	Partially correct
69	Partially correct	72 ms	13416 KB	Partially correct
70	Correct	61 ms	12280 KB	Output is correct
71	Partially correct	42 ms	9060 KB	Partially correct
72	Partially correct	45 ms	10592 KB	Partially correct
73	Correct	62 ms	13372 KB	Output is correct
74	Partially correct	53 ms	12064 KB	Partially correct
75	Partially correct	91 ms	13272 KB	Partially correct
76	Partially correct	88 ms	12732 KB	Partially correct
77	Correct	82 ms	12908 KB	Output is correct
78	Correct	42 ms	8528 KB	Output is correct
79	Partially correct	48 ms	10160 KB	Partially correct
80	Partially correct	131 ms	13292 KB	Partially correct
81	Partially correct	68 ms	12748 KB	Partially correct
82	Partially correct	63 ms	12628 KB	Partially correct