Submission #738702

#	Time	Username	Problem	Language	Result	Execution time	Memory
738702		Stickfish	Village (BOI20_village)	C++17	50 / 100	141 ms	17004 KiB

Village

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <numeric>
using namespace std;

const int MAXN = 1e5 + 123;
vector<int> edg[MAXN];
bitset<MAXN> used;
int rt[MAXN];

bool dfs_getmark(int v, bitset<MAXN>& mark) {
    bool is_edge = false;
    for (auto u : edg[v]) {
        if (u == rt[v])
            continue;
        rt[u] = v;
        is_edge |= dfs_getmark(u, mark);
    }
    if (v == 0) {
        mark[v] = 1;
        if (is_edge)
            return true;
        for (auto u : edg[v]) {
            if (u == rt[v])
                continue;
            mark[u] = 0;
            return true;
        }
    }
    if (is_edge)
        mark[v] = 1;
    return !is_edge;
}

void dfs_onmark(int v, bitset<MAXN>& mark, vector<int>& ans) {
    ans.push_back(v);
    for (auto u : edg[v]) {
        if (u == rt[v] || mark[u])
            continue;
        dfs_onmark(u, mark, ans);
    }
}

pair<int, vector<int>> solve_min(int n) {
    used = 0;
    bitset<MAXN> mark;
    dfs_getmark(0, mark);
    vector<int> ans(n);
    for (int i = 0; i < n; i = mark._Find_next(i)) {
        vector<int> ccl;
        dfs_onmark(i, mark, ccl);
        int m = ccl.size();
        for (int j = 0; j < m; ++j) {
            ans[ccl[j]] = ccl[(j + 1) % m];
        }
    }
    return {2 * (n - mark.count()), ans};
}


pair<int, vector<int>> solve_max(int n) {
    vector<int> pmt(n);
    iota(pmt.begin(), pmt.end(), 0);
    return {1, pmt};
    vector<int> cpmt = pmt;
    do {

        next_permutation(pmt.begin(), pmt.end());
    } while (pmt != cpmt);
}

signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edg[u].push_back(v);
        edg[v].push_back(u);
    }
    auto ansmn = solve_min(n);
    auto ansmx = solve_max(n);
    cout << ansmn.first << ' ' << ansmx.first << '\n';
    for (auto x : ansmn.second)
        cout << x + 1 << ' ';
    cout << '\n';
    for (auto x : ansmx.second)
        cout << x + 1 << ' ';
    cout << '\n';
}

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