Submission #343029

#TimeUsernameProblemLanguageResultExecution timeMemory
343029urd05Village (BOI20_village)C++14
50 / 100
148 ms24300 KiB
#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("1\n"); 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 (stderr)

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:125:9: warning: unused variable 'now' [-Wunused-variable]
  125 |     int now=bfs(0);
      |         ^~~
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);
      |         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...