제출 #343112

#제출 시각아이디문제언어결과실행 시간메모리
343112urd05Village (BOI20_village)C++14
100 / 100
215 ms91492 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]; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...