Submission #1044757

#TimeUsernameProblemLanguageResultExecution timeMemory
1044757goodspeed0208Village (BOI20_village)C++14
100 / 100
61 ms17104 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; int y = x; for (auto i : G[x]) { if (i == p) continue; bool can = dfs(i, x); if (can) { minn += 2; minans[y] = i; minans[i] = x; y = i; //c.push_back(i); } } if (x == 0 && y == x) { minn += 2; minans[x] = minans[G[x][0]]; minans[G[x][0]] = x; } if (y == x) return 1; else return 0; //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); for (int i = 0 ; i < n ; i++) minans[i] = i; 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 'int main()':
Village.cpp:107:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  107 |  for (auto i : minans) cout << i+1 << " "; cout << "\n";
      |  ^~~
Village.cpp:107:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  107 |  for (auto i : minans) cout << i+1 << " "; cout << "\n";
      |                                            ^~~~
Village.cpp:108:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  108 |  for (auto i : maxans) cout << i+1 << " "; cout << "\n";
      |  ^~~
Village.cpp:108:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  108 |  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...