Submission #1275998

#TimeUsernameProblemLanguageResultExecution timeMemory
1275998julia_08Village (BOI20_village)C++20
0 / 100
2 ms12352 KiB
#include <bits/stdc++.h> #define int long long using namespace std; using ll = long long; const int MAXN = 1e5 + 10; int p[MAXN]; int deg[MAXN], marc[MAXN]; vector<int> adj[MAXN], c[MAXN]; int32_t main(){ cin.tie(0)->sync_with_stdio(0); int n; cin >> n; for(int i=1; i<n; i++){ int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); deg[a] ++; deg[b] ++; } queue<int> q; for(int i=1; i<=n; i++){ if(deg[i] == 1){ q.push(i); } } int ans = 0; while(!q.empty()){ int v = q.front(); q.pop(); if(!c[v].empty()){ marc[v] = 1; int sz = (int) c[v].size(); ans += 2 * sz; if(sz % 2 == 0){ while(sz > 2){ auto [a, b] = make_pair(c[v][sz - 2], c[v][sz - 1]); p[a] = b; p[b] = a; sz -= 2; } auto [a, b] = make_pair(c[v][0], c[v][1]); p[v] = a; p[b] = v; p[a] = b; } else{ while(sz > 1){ auto [a, b] = make_pair(c[v][sz - 2], c[v][sz - 1]); p[a] = b; p[b] = a; sz -= 2; } p[v] = c[v][0]; p[c[v][0]] = v; } } for(auto u : adj[v]){ deg[u] --; if(!marc[v]) c[u].push_back(v); if(deg[u] == 1) q.push(u); } } cout << ans << " 1 " << "\n"; for(int i=1; i<=n; i++) cout << p[i] << " "; cout << "\n"; for(int i=1; i<=n; i++) cout << "1 "; cout << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...