| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 343027 |
2021-01-03T11:17:32 Z |
urd05 |
Village (BOI20_village) |
C++14 |
|
0 ms |
0 KB |
#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];
void dfs(int v,int prev) {
p[v]=prev;
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);
}
}
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;
bool visited[100000];
bool gone[100000];
vector<int> v;
int dist[100000];
int bfs(int u) {
memset(visited,0,sizeof(visited));
dist[u]=0;
queue<int> q;
q.push(u);
visited[u]=true;
while (!q.empty()) {
int now=q.front();
q.pop();
for(int i=0;i<adj[now].size();i++) {
int nt=adj[now][i];
if (!gone[nt]&&!visited[nt]) {
visited[nt]=true;
q.push(nt);
dist[nt]=dist[now]+1;
}
}
}
int pos=u;
for(int i=0;i<n;i++) {
if (!gone[i]&&dist[i]>dist[pos]) {
pos=i;
}
}
return pos;
}
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 main(void) {
memset(save,-1,sizeof(save));
scanf("%d",&n);
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(0,-1);
printf("%d ",2*n-2*dp0[0]);
int now=bfs(0);
/*
v.push_back(now);
int ret=0;
int st=now;
for(int cnt=0;cnt+1<n;cnt++) {
int save=now;
now=bfs(now);
gone[save]=true;
v.push_back(now);
ret+=dist[now];
}*/
memset(gone,0,sizeof(gone));
bfs(now);
ret+=dist[st];
printf("%d\n",ret);
dfs2(0,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);
}
}
Compilation message
Village.cpp: In function 'void dfs(int, int)':
Village.cpp:16:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i=0;i<son[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i=0;i<son[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp: In function 'int bfs(int)':
Village.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i=0;i<adj[now].size();i++) {
| ~^~~~~~~~~~~~~~~~
Village.cpp: In function 'void dfs2(int, int)':
Village.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i=0;i<son[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp:86:22: 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<son[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int i=0;i<son[v].size();i++) {
| ~^~~~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:139:5: error: 'ret' was not declared in this scope
139 | ret+=dist[st];
| ^~~
Village.cpp:139:15: error: 'st' was not declared in this scope; did you mean 'std'?
139 | ret+=dist[st];
| ^~
| std
Village.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
114 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
Village.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
117 | scanf("%d %d",&u,&v);
| ~~~~~^~~~~~~~~~~~~~~
