이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100000];
vector<int> son[100000];
int dp0[100000];
int dp1[100000];
int p[100000];
int group[100000];
int save[100000];
int nxt[100000];
int nxt2[100000];
int sz[100000];
typedef pair<int,int> P;
void dfs(int v,int prev) {
p[v]=prev;
sz[v]=1;
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt!=prev) {
son[v].push_back(nt);
dfs(nt,v);
sz[v]+=sz[nt];
}
}
for(int i=0;i<son[v].size();i++) {
int nt=son[v][i];
dp1[v]+=max(dp0[nt],dp1[nt]);
}
int mx=-1e6;
dp0[v]=1;
for(int i=0;i<son[v].size();i++) {
int nt=son[v][i];
mx=max(mx,dp1[nt]-dp0[nt]);
dp0[v]+=max(dp0[nt],dp1[nt]);
}
if (mx<0) {
dp0[v]+=mx;
}
}
int n;
vector<int> v;
void dfs2(int v,int type) {
if (type==0) {
group[v]=v;
save[v]=v;
int pos=-1;
int mx=-1e6;
for(int i=0;i<son[v].size();i++) {
int nt=son[v][i];
if (dp1[nt]-dp0[nt]>mx) {
mx=dp1[nt]-dp0[nt];
pos=i;
}
}
for(int i=0;i<son[v].size();i++) {
int nt=son[v][i];
if (dp1[nt]>dp0[nt]||pos==i) {
dfs2(nt,1);
}
else {
dfs2(nt,0);
}
}
}
else {
group[v]=group[p[v]];
nxt[v]=save[group[v]];
save[group[v]]=v;
for(int i=0;i<son[v].size();i++) {
int nt=son[v][i];
if (dp1[nt]>dp0[nt]) {
dfs2(nt,1);
}
else {
dfs2(nt,0);
}
}
}
}
int getcent(int v,int prev,int half) {
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt==prev) {
continue;
}
if (sz[nt]>half) {
return getcent(nt,v,half);
}
}
return v;
}
stack<int> s[100000];
void psh(int v,int type) {
s[type].push(v);
for(int i=0;i<son[v].size();i++) {
psh(son[v][i],type);
}
}
void dfs_sz(int v,int prev) {
sz[v]=1;
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt==prev) {
continue;
}
dfs_sz(nt,v);
sz[v]+=sz[nt];
}
}
int main(void) {
memset(save,-1,sizeof(save));
scanf("%d",&n);
if (n==2) {
printf("2 2\n2 1\n2 1");
return 0;
}
for(int i=1;i<n;i++) {
int u,v;
scanf("%d %d",&u,&v);
u--;
v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs_sz(0,-1);
int cent=getcent(0,-1,n/2);
dfs(cent,-1);
printf("%d ",2*n-2*dp0[cent]);
long long ret=0;
for(int i=0;i<n;i++) {
if (i!=cent)
ret+=min(sz[i],n-sz[i])*2;
}
printf("%lld\n",ret);
priority_queue<P> pq;
for(int i=0;i<son[cent].size();i++) {
pq.push(P(sz[son[cent][i]],i));
psh(son[cent][i],i);
}
v.push_back(cent);
int prev=-1;
for(int i=1;i<n;i++) {
P now=pq.top();
P sav=P(-1,-1);
if (now.second==prev) {
sav=now;
pq.pop();
now=pq.top();
}
v.push_back(s[now.second].top());
s[now.second].pop();
pq.pop();
pq.push(P(now.first-1,now.second));
if (sav.second!=-1) {
pq.push(sav);
}
prev=now.second;
}
for(int i=0;i<n;i++) {
nxt2[v[i]]=v[(i+1)%n];
}
dfs2(cent,0);
for(int i=0;i<n;i++) {
if (save[i]!=-1) {
nxt[i]=save[i];
}
}
for(int i=0;i<n;i++) {
printf("%d ",nxt[i]+1);
}
printf("\n");
for(int i=0;i<n;i++) {
printf("%d ",nxt2[i]+1);
}
}
컴파일 시 표준 에러 (stderr) 메시지
Village.cpp: In function 'void dfs(int, int)':
Village.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int i=0;i<son[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i=0;i<son[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp: In function 'void dfs2(int, int)':
Village.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i=0;i<son[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i=0;i<son[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i=0;i<son[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp: In function 'int getcent(int, int, int)':
Village.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp: In function 'void psh(int, int)':
Village.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int i=0;i<son[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp: In function 'void dfs_sz(int, int)':
Village.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:145:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for(int i=0;i<son[cent].size();i++) {
| ~^~~~~~~~~~~~~~~~~
Village.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
121 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
Village.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
128 | scanf("%d %d",&u,&v);
| ~~~~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |