답안 #654914

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654914	2022-11-02T00:39:53 Z	inksamurai	Village (BOI20_village)	C++17	50 / 100	138 ms	27544 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	1 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	0 ms	212 KB	Output is correct
10	Partially correct	0 ms	212 KB	Partially correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 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	1 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	0 ms	212 KB	Output is correct
10	Partially correct	0 ms	212 KB	Partially correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 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	69 ms	11800 KB	Partially correct
49	Correct	83 ms	12996 KB	Output is correct
50	Partially correct	83 ms	12888 KB	Partially correct
51	Partially correct	54 ms	9972 KB	Partially correct
52	Partially correct	85 ms	12396 KB	Partially correct
53	Partially correct	95 ms	11540 KB	Partially correct
54	Correct	39 ms	13300 KB	Output is correct
55	Correct	138 ms	27544 KB	Output is correct
56	Partially correct	109 ms	19940 KB	Partially correct
57	Partially correct	105 ms	17508 KB	Partially correct
58	Partially correct	96 ms	15316 KB	Partially correct
59	Partially correct	79 ms	13116 KB	Partially correct
60	Correct	53 ms	12588 KB	Output is correct
61	Partially correct	56 ms	12608 KB	Partially correct
62	Correct	58 ms	13256 KB	Output is correct
63	Partially correct	54 ms	12396 KB	Partially correct
64	Partially correct	64 ms	12864 KB	Partially correct
65	Correct	62 ms	13628 KB	Output is correct
66	Correct	55 ms	12108 KB	Output is correct
67	Partially correct	46 ms	9752 KB	Partially correct
68	Partially correct	50 ms	11192 KB	Partially correct
69	Partially correct	61 ms	13424 KB	Partially correct
70	Correct	53 ms	12296 KB	Output is correct
71	Partially correct	37 ms	9096 KB	Partially correct
72	Partially correct	42 ms	10556 KB	Partially correct
73	Correct	72 ms	13380 KB	Output is correct
74	Partially correct	52 ms	12032 KB	Partially correct
75	Partially correct	86 ms	13212 KB	Partially correct
76	Partially correct	73 ms	12744 KB	Partially correct
77	Correct	78 ms	12880 KB	Output is correct
78	Correct	39 ms	8520 KB	Output is correct
79	Partially correct	52 ms	10148 KB	Partially correct
80	Partially correct	90 ms	13312 KB	Partially correct
81	Partially correct	64 ms	12780 KB	Partially correct
82	Partially correct	61 ms	12604 KB	Partially correct