Submission #857936

#	Time	Username	Problem	Language	Result	Execution time	Memory
857936		Trisanu_Das	Village (BOI20_village)	C++17	25 / 100	875 ms	13540 KiB

Village

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

const int maxn = 1e5 + 1;
vector<int> adj[maxn];
int deg[maxn], pos[maxn];
 
int main() {
    int n; cin >> n;
    int a, b;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        --a, --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        ++deg[a], ++deg[b];
        pos[i] = i;
    }
    pos[n - 1] = n - 1;
    unordered_set<int> leafs;
    for (int i = 0; i < n; i++) if (deg[i] == 1) leafs.insert(i);
    int sol = 0;
    while (!leafs.empty()) {
        int cur = *leafs.begin();
        leafs.erase(leafs.begin());
        int next = adj[cur][0];
        if (pos[cur] == cur) {
            sol += 2;
            swap(pos[cur], pos[next]);
        }
        if (--deg[next] == 1) leafs.insert(adj[cur][0]);
        adj[next].erase(find(adj[next].begin(), adj[next].end(), cur));
    }
    cout << sol << ' ' << 1 << '\n';
    vector<int> loc(n);
    for (int i = 0; i < n; i++) {
        loc[pos[i]] = i;
        assert(pos[i] != i);
    }
    for (int i = 0; i < n; i++) cout << loc[i] + 1 << ' ';
    cout << '\n';
    for (int i = 0; i < n; i++) cout << 1 << ' ';
    cout << '\n';
}

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