Submission #332681

#	Time	Username	Problem	Language	Result	Execution time	Memory
332681		izhang05	Village (BOI20_village)	C++17	25 / 100	1083 ms	12156 KiB

Village

#include <bits/stdc++.h>

using namespace std;

mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count());
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
template<class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>
using indexed_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T>
void print(T a) {
    for (auto i : a) {
        cout << i << " ";
    }
    cout << "\n";
}

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
//freopen("solution.out", "w", stdout);
    freopen("3.in", "r", stdin);
#endif
}

const int maxn = 1e5 + 1;
vector<int> adj[maxn];
int deg[maxn], pos[maxn];

int main() {
    setIO();
    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 - 1; ++i) {
        cout << loc[i] + 1 << " ";
    }
    cout << loc[n - 1] + 1 << "\n";
    for (int i = 0; i < n - 1; ++i) {
        cout << 1 << " ";
    }
    cout << 1 << "\n";
    return 0;
}

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