Submission #656304

#	Time	Username	Problem	Language	Result	Execution time	Memory
656304		esomer	Village (BOI20_village)	C++17	50 / 100	76 ms	20172 KiB

Village

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

const int MOD = 998244353;

vector<int> v;
int ans = 0;

bool DFS(int x, vector<vector<int>>& adj, int p){
    vector<int> odd;
    for(int node : adj[x]){
        if(node == p) continue;
        bool rep = DFS(node, adj, x);
        if(rep) odd.push_back(node);
    }
    if(odd.size() == 0){
        if(x == 0){
            int node = adj[x][0];
            if(v[v[node]] == node){
                v[x] = v[node];
                v[node] = x;
                ans += 2;
            }else{
                int node1 = v[node];
                int node2 = v[v[node]];
                v[node1] = node2;
                v[node2] = node1;
                v[x] = node;
                v[node] = x;
                ans += 2;
            }
        }else return 1;
    }else{
        if(((int)odd.size()) % 2 == 1){
            for(int i = 1; i < (int)odd.size() - 1; i += 2){
                v[odd[i]] = odd[i + 1];
                v[odd[i + 1]] = odd[i];
                ans += 4;
            }
            v[x] = odd[0];
            v[odd[0]] = x;
            ans += 2;
        }else{
            for(int i = 2; i < (int)odd.size() - 1; i += 2){
                v[odd[i]] = odd[i + 1];
                v[odd[i + 1]] = odd[i];
                ans += 4;
            }
            v[x] = odd[0];
            v[odd[0]] = odd[1];
            v[odd[1]] = x;
            ans += 4;
        }
    }
    return 0;
}

void solve(){
    int n; cin >> n;
    v.resize(n);
    vector<vector<int>> adj(n);
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b; a--; b--;
        adj[a].push_back(b); adj[b].push_back(a);
    }
    DFS(0, adj, -1);
    cout << ans << " "<<-1 << endl;
    for(int x : v) cout << x + 1 << " ";
    cout << endl;
    for(int i = 0; i < n; i++) cout << 1 << " ";
    cout << endl;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    //freopen("inpt.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    //int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        //cout << "Case #"<<t << ": ";
        solve();
    }
}

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50