Submission #1044743

#TimeUsernameProblemLanguageResultExecution timeMemory
1044743goodspeed0208Village (BOI20_village)C++14
0 / 100
1 ms600 KiB
#include<bits/stdc++.h> #define int long long #define pii pair<long long, long long> using namespace std; int n, minn = 0, maxx = 0; vector<vector<int> >G; vector<int>minans; vector<int>maxans; bool dfs(int x, int p) { vector<int>c; for (auto i : G[x]) { if (i == p) continue; bool can = dfs(i, x); if (can) { c.push_back(i); } } //cout << x <<" " << c.size() << "\n"; for (int i = 0 ; i < c.size()/2 ; i++) { minn += 4; minans[c[i*2]] = c[i*2+1]; minans[c[i*2+1]] = c[i*2]; } if (c.size() % 2 == 1) { minn += 2; minans[c.back()] = x; minans[x] = c.back(); return 0; } else { if (x == 0) { if (c.size() > 0) { minans[c[0]] = x; minans[x] = c[1]; } else { minn += 2; minans[x] = minans[G[x][0]]; minans[G[x][0]] = x; } return 0; } return 1; } } int cnt; int findc(int x, int p) { int num = 1; bool can = 1; for (auto i : G[x]) { if (i == p) continue; int child = findc(i, x); if (child > n/2) can = 0; num += child; } if (n - num > n/2) can = 0; if (can) cnt = x; return num; } vector<int>arr; void dis(int x, int p, int d) { maxx += d*2; arr.push_back(x); for (auto i : G[x]) { if (i == p) continue; dis(i, x, d+1); } } signed main() { cin >> n; G.resize(n); minans.resize(n); maxans.resize(n); int a, b; for (int i = 0 ; i < n-1 ; i++){ cin >> a >> b; a--, b--; G[a].push_back(b); G[b].push_back(a); } dfs(0, -1); findc(0, -1); dis(cnt, -1, 0); for (int i = 0 ; i < n ; i++) { //cout << arr[i] <<" "; maxans[arr[i]] = arr[(i+n/2)%n]; } //cout <<"\n"; assert(minn == ((n+1) / 2) * 2); cout << minn << " " << maxx << "\n"; for (auto i : minans) cout << i+1 << " "; cout << "\n"; for (auto i : maxans) cout << i+1 << " "; cout << "\n"; }

Compilation message (stderr)

Village.cpp: In function 'bool dfs(long long int, long long int)':
Village.cpp:21:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int i = 0 ; i < c.size()/2 ; i++) {
      |                   ~~^~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:94:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   94 |  for (auto i : minans) cout << i+1 << " "; cout << "\n";
      |  ^~~
Village.cpp:94:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   94 |  for (auto i : minans) cout << i+1 << " "; cout << "\n";
      |                                            ^~~~
Village.cpp:95:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   95 |  for (auto i : maxans) cout << i+1 << " "; cout << "\n";
      |  ^~~
Village.cpp:95:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   95 |  for (auto i : maxans) cout << i+1 << " "; cout << "\n";
      |                                            ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...