oj.uz

Submission #738700

# Submission time Handle Problem Language Result Execution time Memory
738700 2023-05-09T12:30:07 Z Stickfish Village (BOI20_village) C++17
0 / 100
 306 ms 262144 KB 
#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; ++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
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 2644 KB Partially correct
2 Partially correct 2 ms 2644 KB Partially correct
3 Runtime error 4 ms 5212 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 306 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 2644 KB Partially correct
2 Partially correct 2 ms 2644 KB Partially correct
3 Runtime error 4 ms 5212 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -