oj.uz

Submission #714398

# Submission time Handle Problem Language Result Execution time Memory
714398 2023-03-24T10:15:47 Z Stickfish Demarcation (BOI14_demarcation) C++17
0 / 100
 45 ms 59908 KB 
#include <iostream>
#include <unordered_set>
#include <cassert>
#include <bitset>
#include <vector>
using namespace std;

const int MAXN = 5e5 + 123;
unordered_set<int> edg[MAXN];

void find_euler_cycle(int v, vector<int>& ans) {
    while (edg[v].size()) {
        int u = *edg[v].begin();
        edg[v].erase(u);
        edg[u].erase(v);
        find_euler_cycle(u, ans);
    }
    ans.push_back(v);
}

signed main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edg[u].insert(v);
        edg[v].insert(u);
    }
    vector<int> ans;
    find_euler_cycle(0, ans);

    //for (auto x : ans)
        //cout << x + 1 << ' ';
    //cout << endl;

    vector<int> stck;
    bitset<MAXN> used;
    for (auto x : ans) {
        vector<int> ccl;
        while (used[x]) {
            used[stck.back()] = 0;
            ccl.push_back(stck.back());
            stck.pop_back();
        }
        if (ccl.size()) {
            for (auto x : ccl)
                cout << x + 1 << ' ';
            cout << '\n';
        }
        stck.push_back(x);
        used[x] = 1;
    }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 59872 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 58704 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 58632 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 59908 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -