제출 #1093073

#제출 시각아이디문제언어결과실행 시간메모리
1093073Jakub_WozniakVillage (BOI20_village)C++14
50 / 100
101 ms51380 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define nd second #define st first typedef pair<ll, ll> pii; const int maxn = (1e+5)+9; vector <ll> t[maxn]; ll siz[maxn]; ll dep[maxn]; ll sumdep[maxn]; ll cen = -1; ll dp[maxn][2]; vector<pii> resmin[maxn][2]; ll tabmin[maxn]; ll tabmax[maxn]; vector <int> podd[maxn]; ll N; void rek(int v , int o , int re) { set <int> V[2]; ll mini = (1e+18); bool B = 0; int p , ind = -1; for(int i = 0 ;i < t[v].size();i++) { p = t[v][i]; if(p == o)continue; if(dp[p][1]+2 <= dp[p][0]) { V[1].insert(p); B = 1; } else { V[0].insert(p); if(dp[p][1]+2-dp[p][0] < mini)ind = p; mini = min(dp[p][1]+2-dp[p][0] , mini); } } if(B == 0 && re == 0) { V[0].erase(ind); V[1].insert(ind); } for(auto it = V[1].begin() ; it != V[1].end() ; it++) { rek(*it,v,1); } for(auto it = V[0].begin() ; it != V[0].end() ; it++) { rek(*it,v,0); } if(re == 0)V[1].insert(v); vector <int> vec; for(auto it = V[1].begin() ; it != V[1].end() ; it++) { vec.push_back(*it); } for(int i = 0 ; i < vec.size() ;i++) { tabmin[vec[i]] = vec[(i+1)%vec.size()]; } } void DFS(int v , int o) { ll ind = -1; ll p , res = 0; bool B = 0; ll mini = (1e+18); for(int i = 0 ;i < t[v].size();i++) { p = t[v][i]; if(p == o)continue; DFS(p,v); if(dp[p][1]+2 <= dp[p][0]) { res += dp[p][1]+2; B = 1; } else { res += dp[p][0]; if(dp[p][1]+2-dp[p][0] < mini)ind = p; mini = min(dp[p][1]+2-dp[p][0] , mini); } } dp[v][1] = res; if(B == 0) { res += mini; } dp[v][0] = res; if(v == 1) { rek(1,-1,0); } } void DFS2(int v, int o) { siz[v] = 1; int p , pmax = 0; for(int i = 0; i < t[v].size() ;i++) { p = t[v][i]; if(p == o)continue; DFS2(p,v); pmax = max((ll)pmax,siz[p]); siz[v] += siz[p]; } pmax = max((ll)pmax,N-siz[v]); if(pmax <= N/2)cen = v; } void DFS3(int v ,int o , int c) { podd[c].push_back(v); sumdep[v] = dep[v]; int p; for(int i = 0 ;i < t[v].size() ;i++) { p = t[v][i]; if(p == o)continue; dep[p] = dep[v]+1; DFS3(p,v,c); sumdep[v] += sumdep[p]; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll A , B; cin >> N; for(int i = 0 ;i < N-1 ; i++) { cin >> A >> B; t[A].push_back(B); t[B].push_back(A); } if(N == 2) { cout << 2 << ' ' << 2 << '\n'; cout << 2 << ' ' << 1 << '\n'; cout << 2 << ' ' << 1 << '\n'; return 0; } priority_queue <pii> q; ll ansmax = 0; DFS2(1,-1); podd[cen].push_back(cen); for(int i = 0 ; i < t[cen].size() ;i++) { dep[t[cen][i]] = 1; DFS3(t[cen][i],cen,t[cen][i]); ansmax += sumdep[t[cen][i]]; q.push({podd[t[cen][i]].size(),t[cen][i]}); } if(N%2) { A = q.top().nd; q.pop(); B = q.top().nd; q.pop(); tabmax[podd[A][podd[A].size()-1]] = cen; tabmax[cen] = podd[B][podd[B].size()-1]; tabmax[podd[B][podd[B].size()-1]] = podd[A][podd[A].size()-1]; podd[A].pop_back(); podd[B].pop_back(); if(podd[A].size() > 0)q.push({podd[A].size(),A}); if(podd[B].size() > 0)q.push({podd[B].size(),B}); } else { q.push({1,cen}); } while(!q.empty()) { A = q.top().nd; q.pop(); B = q.top().nd; q.pop(); tabmax[podd[A][podd[A].size()-1]] = podd[B][podd[B].size()-1]; tabmax[podd[B][podd[B].size()-1]] = podd[A][podd[A].size()-1]; podd[A].pop_back(); podd[B].pop_back(); if(podd[A].size() > 0)q.push({podd[A].size(),A}); if(podd[B].size() > 0)q.push({podd[B].size(),B}); } DFS(1,-1); cout << dp[1][0] << ' ' << ansmax*2 << '\n'; for(int i = 1 ; i <= N ; i++)cout << tabmin[i] << ' '; cout << '\n'; for(int i = 1 ; i <= N ; i++)cout << tabmax[i] << ' '; cout << '\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Village.cpp: In function 'void rek(int, int, int)':
Village.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0 ;i < t[v].size();i++)
      |                    ~~^~~~~~~~~~~~~
Village.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 0 ; i < vec.size() ;i++)
      |                     ~~^~~~~~~~~~~~
Village.cpp: In function 'void DFS(int, int)':
Village.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = 0 ;i < t[v].size();i++)
      |                    ~~^~~~~~~~~~~~~
Village.cpp:75:8: warning: variable 'ind' set but not used [-Wunused-but-set-variable]
   75 |     ll ind = -1;
      |        ^~~
Village.cpp: In function 'void DFS2(int, int)':
Village.cpp:115:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i = 0; i < t[v].size() ;i++)
      |                    ~~^~~~~~~~~~~~~
Village.cpp: In function 'void DFS3(int, int, int)':
Village.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for(int i = 0 ;i < t[v].size() ;i++)
      |                    ~~^~~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:169:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |     for(int i = 0 ; i < t[cen].size() ;i++)
      |                     ~~^~~~~~~~~~~~~~~
Village.cpp:222:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  222 |     for(int i = 1 ; i <= N ; i++)cout << tabmin[i] << ' '; cout << '\n';
      |     ^~~
Village.cpp:222:60: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  222 |     for(int i = 1 ; i <= N ; i++)cout << tabmin[i] << ' '; cout << '\n';
      |                                                            ^~~~
Village.cpp:223:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  223 |     for(int i = 1 ; i <= N ; i++)cout << tabmax[i] << ' '; cout << '\n';
      |     ^~~
Village.cpp:223:60: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  223 |     for(int i = 1 ; i <= N ; i++)cout << tabmax[i] << ' '; cout << '\n';
      |                                                            ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...