Submission #946014

#TimeUsernameProblemLanguageResultExecution timeMemory
946014LucaIlieVillage (BOI20_village)C++17
50 / 100
94 ms17368 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 1e5; int sizee[MAX_N + 1], depth[MAX_N + 1], pairr[MAX_N + 1]; vector<int> adj[MAX_N + 1]; int n; int c; void findCentroid( int u, int p ) { int maxSizee = 0; sizee[u] = 1; for ( int v: adj[u] ) { if ( v == p ) continue; findCentroid( v, u ); sizee[u] += sizee[v]; maxSizee = max( maxSizee, sizee[v] ); } maxSizee = max( maxSizee, n - sizee[u] ); if ( maxSizee <= n / 2 ) c = u; } void calcSizes( int u, int p ) { sizee[u] = 1; for ( int v: adj[u] ) { if ( v == p ) continue; calcSizes( v, u ); sizee[u] += sizee[v]; } } long long maxSumDist; vector<int> vert; void dfs( int u, int p ) { depth[u] = depth[p] + 1; maxSumDist += depth[u]; for ( int v: adj[u] ) { if ( v == p ) continue; dfs( v, u ); } vert.push_back( u ); } int main() { cin >> n; for ( int i = 0; i < n - 1; i++ ) { int u, v; cin >> u >> v; adj[u].push_back( v ); adj[v].push_back( u ); } findCentroid( 1, 0 ); depth[0] = -1; dfs( c, 0 ); for ( int i = 0; i < n / 2; i++ ) { pairr[vert[i]] = vert[n / 2 + i]; pairr[vert[n / 2 + i]] = vert[i]; } if ( pairr[c] == 0 ) { int a = adj[c][0], b = pairr[a]; pairr[a] = b; pairr[b] = c; pairr[c] = a; } cout << 1 << " " << 2 * maxSumDist << "\n"; for ( int v = 1; v <= n; v++ ) cout << v << " "; cout << "\n"; for ( int v = 1; v <= n; v++ ) cout << pairr[v] << " "; cout << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...