답안 #654916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654916	2022-11-02T00:41:57 Z	inksamurai	Village (BOI20_village)	C++17	50 / 100	166 ms	31140 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;
	assert(sz(set<int>(all(ert1)))==n);
	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	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	468 KB	Partially correct
5	Partially correct	1 ms	468 KB	Partially correct
6	Partially correct	1 ms	468 KB	Partially correct
7	Correct	1 ms	468 KB	Output is correct
8	Partially correct	1 ms	468 KB	Partially correct
9	Partially correct	1 ms	468 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	468 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Partially correct	1 ms	468 KB	Partially correct
15	Partially correct	1 ms	468 KB	Partially correct
16	Correct	1 ms	468 KB	Output is correct
17	Partially correct	1 ms	468 KB	Partially correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	1 ms	468 KB	Output is correct
20	Correct	1 ms	468 KB	Output is correct
21	Partially correct	1 ms	468 KB	Partially correct
22	Partially correct	1 ms	468 KB	Partially correct
23	Partially correct	1 ms	340 KB	Partially correct
24	Partially correct	1 ms	468 KB	Partially correct
25	Correct	1 ms	340 KB	Output is correct
26	Partially correct	1 ms	468 KB	Partially correct
27	Partially correct	1 ms	340 KB	Partially correct
28	Partially correct	1 ms	468 KB	Partially correct
29	Partially correct	1 ms	468 KB	Partially correct
30	Partially correct	1 ms	468 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	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	468 KB	Partially correct
22	Partially correct	1 ms	468 KB	Partially correct
23	Partially correct	1 ms	468 KB	Partially correct
24	Correct	1 ms	468 KB	Output is correct
25	Partially correct	1 ms	468 KB	Partially correct
26	Partially correct	1 ms	468 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	468 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Partially correct	1 ms	468 KB	Partially correct
32	Partially correct	1 ms	468 KB	Partially correct
33	Correct	1 ms	468 KB	Output is correct
34	Partially correct	1 ms	468 KB	Partially correct
35	Correct	1 ms	468 KB	Output is correct
36	Correct	1 ms	468 KB	Output is correct
37	Correct	1 ms	468 KB	Output is correct
38	Partially correct	1 ms	468 KB	Partially correct
39	Partially correct	1 ms	468 KB	Partially correct
40	Partially correct	1 ms	340 KB	Partially correct
41	Partially correct	1 ms	468 KB	Partially correct
42	Correct	1 ms	340 KB	Output is correct
43	Partially correct	1 ms	468 KB	Partially correct
44	Partially correct	1 ms	340 KB	Partially correct
45	Partially correct	1 ms	468 KB	Partially correct
46	Partially correct	1 ms	468 KB	Partially correct
47	Partially correct	1 ms	468 KB	Partially correct
48	Partially correct	99 ms	14960 KB	Partially correct
49	Correct	134 ms	16568 KB	Output is correct
50	Partially correct	103 ms	16452 KB	Partially correct
51	Partially correct	81 ms	12908 KB	Partially correct
52	Partially correct	107 ms	16204 KB	Partially correct
53	Partially correct	101 ms	14740 KB	Partially correct
54	Correct	57 ms	15112 KB	Output is correct
55	Correct	143 ms	31140 KB	Output is correct
56	Partially correct	137 ms	23752 KB	Partially correct
57	Partially correct	130 ms	21140 KB	Partially correct
58	Partially correct	166 ms	19132 KB	Partially correct
59	Partially correct	115 ms	16840 KB	Partially correct
60	Correct	89 ms	16260 KB	Output is correct
61	Partially correct	85 ms	16584 KB	Partially correct
62	Correct	94 ms	16848 KB	Output is correct
63	Partially correct	93 ms	15724 KB	Partially correct
64	Partially correct	103 ms	16796 KB	Partially correct
65	Correct	101 ms	17084 KB	Output is correct
66	Correct	86 ms	15788 KB	Output is correct
67	Partially correct	58 ms	12368 KB	Partially correct
68	Partially correct	82 ms	14384 KB	Partially correct
69	Partially correct	95 ms	17000 KB	Partially correct
70	Correct	86 ms	15980 KB	Output is correct
71	Partially correct	62 ms	11860 KB	Partially correct
72	Partially correct	65 ms	13536 KB	Partially correct
73	Correct	92 ms	16956 KB	Output is correct
74	Partially correct	81 ms	15568 KB	Partially correct
75	Partially correct	113 ms	16956 KB	Partially correct
76	Partially correct	109 ms	16444 KB	Partially correct
77	Correct	96 ms	16236 KB	Output is correct
78	Correct	57 ms	11144 KB	Output is correct
79	Partially correct	75 ms	12968 KB	Partially correct
80	Partially correct	109 ms	16944 KB	Partially correct
81	Partially correct	98 ms	16184 KB	Partially correct
82	Partially correct	89 ms	16324 KB	Partially correct