oj.uz

Submission #517308

# Submission time Handle Problem Language Result Execution time Memory
517308 2022-01-23T01:57:17 Z KoD Slagalica (COCI19_slagalica2) C++17
70 / 70
 39 ms 5836 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    array<vector<pair<int, int>>, 2> graph = {};
    array<array<int, 2>, 2> count = {};
    int src = -1, dst = -1, src_id = -1, dst_id = -1;
    for (int i = 0; i < N; ++i) {
        int x, a;
        std::cin >> x >> a;
        if (x == 1) graph[0].emplace_back(a, 1), count[0][1] += 1;
        if (x == 2) graph[0].emplace_back(a, 0), count[0][0] += 1;
        if (x == 3) graph[1].emplace_back(a, 1), count[1][1] += 1;
        if (x == 4) graph[1].emplace_back(a, 0), count[1][0] += 1;
        if (x == 5) src = 1, src_id = a;
        if (x == 6) src = 0, src_id = a;
        if (x == 7) dst = 0, dst_id = a;
        if (x == 8) dst = 1, dst_id = a;
    }
    if ((src == 0) + count[1][0] != (dst == 0) + count[0][1]) {
        std::cout << -1 << '\n';
        return 0;
    }
    for (auto& v : graph) {
        std::sort(v.rbegin(), v.rend());
    }
    vector<int> ans;
    ans.reserve(N - 2);
    RecLambda([&](auto&& dfs, const int u) -> void {
        while (!graph[u].empty()) {
            const auto [a, v] = graph[u].back();
            graph[u].pop_back();
            dfs(v);
            ans.push_back(a);
        }
    })(src);
    if ((int)ans.size() != N - 2) {
        std::cout << -1 << '\n';
        return 0;
    }
    std::reverse(ans.begin(), ans.end());
    std::cout << src_id;
    for (const int x : ans) {
        std::cout << ' ' << x;
    }
    std::cout << ' ' << dst_id << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 316 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5304 KB Output is correct
2 Correct 21 ms 2208 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5164 KB Output is correct
2 Correct 14 ms 2224 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1992 KB Output is correct
2 Correct 31 ms 5240 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1944 KB Output is correct
2 Correct 29 ms 4800 KB Output is correct
3 Correct 32 ms 5468 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4304 KB Output is correct
2 Correct 15 ms 2240 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4992 KB Output is correct
2 Correct 15 ms 2240 KB Output is correct
3 Correct 34 ms 5300 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1984 KB Output is correct
2 Correct 31 ms 5140 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5836 KB Output is correct
2 Correct 14 ms 2276 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5048 KB Output is correct
2 Correct 15 ms 2288 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5828 KB Output is correct
2 Correct 15 ms 2276 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4956 KB Output is correct
2 Correct 19 ms 2224 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5164 KB Output is correct
2 Correct 16 ms 2236 KB Output is correct