Submission #1158156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158156		jasonic	Village (BOI20_village)	C++20	0 / 100	0 ms	324 KiB

Village

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

#define cerr if(false) cerr << "ERR: "

class Compare{public:
    bool operator()(const pair<ll, ll> &a, const pair<ll, ll> &b) {
        return a.first > b.first;
    }
};

ll N;
ll anyChild;
unordered_map<ll, vector<ll>> adjList;
bool swapped[100005];
ll depth[100005];
ll par[100005];
priority_queue<pair<ll, ll>, vector<pair<ll ,ll>>, Compare> thing;

void dfs(ll n, ll p = -1) {
    par[n] = p;
    depth[n] = 0;
    for(auto i:adjList[n]) {
        if (i == p) continue;

        if (n == 0) anyChild = i;
        dfs(i, n);
        depth[n] = max(depth[n], depth[i] + 1);
    }
    thing.emplace(make_pair(depth[n], n));
}

int main() {
    fastIO;

    cin >> N;
    
    for(int i = 0; i < N-1; i++) {
        ll a, b; cin >> a >> b;
        a--;b--;
        adjList[a].push_back(b);
        adjList[b].push_back(a);
    }

    // maybe greedily swap them?
    // swap the houses by depth from leaves?

    dfs(0);
    ll ans = 0;
    vector swaps(N, 0ll);

    for(int i = 0; i < N; i++) swaps[i] = i+1;

    while(!thing.empty()) {
        pair<ll, ll> curr = thing.top(); thing.pop();
        ll node = curr.second;
        if (swapped[node]) continue;

        cerr << node << '\n';

        ans += 2;

        if (node == 0) { // not swapped, swap with any child
            swapped[node] = true;
            swap(swaps[anyChild], swaps[node]);
        } else {
            swapped[node] = true;
            swapped[par[node]] = true;
            swap(swaps[node], swaps[node]);
        }
    }

    cout << ans << " 0\n";
    for(auto &i : swaps) cout << i << ' ';
    cout << '\n';
    for(int i = 0; i < N; i++) cout << i+1 << ' ';
    
    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50