Submission #517313

#	Time	Username	Problem	Language	Result	Execution time	Memory
517313		KoD	Checker (COCI19_checker)	C++17	110 / 110	495 ms	31088 KiB

checker

#include <bits/stdc++.h>

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

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N >> N;
    std::map<pair<int, int>, int> col;
    vector<int> next(N), prev(N);
    for (int i = 0; i < N; ++i) {
        next[i] = i + 1 == N ? 0 : i + 1;
        prev[i] = i == 0 ? N - 1 : i - 1;
        char c;
        std::cin >> c;
        col.emplace(std::minmax(i, next[i]), c - '0');
    }   
    vector<int> deg(N, 2);
    for (int i = 0; i < N - 3; ++i) {
        int u, v, c;
        std::cin >> u >> v >> c;
        u -= 1, v -= 1;
        deg[u] += 1, deg[v] += 1;
        col.emplace(std::minmax(u, v), c);
    }
    const auto get_col = [&](const int u, const int v) {
        auto itr = col.find(std::minmax(u, v));
        return itr == col.end() ? 0 : itr->second;
    };
    std::queue<int> que;
    for (int i = 0; i < N; ++i) {
        if (deg[i] == 2) {
            que.push(i);
        }
    }
    bool triangle = true, color = true;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        if (deg[u] != 2) {
            continue;
        }
        const int v = prev[u], w = next[u];
        const int a = get_col(u, v), b = get_col(v, w), c = get_col(w, u);
        if (a == 0 or b == 0 or c == 0) {
            triangle = false;
            break;
        }
        if ((a - b) * (b - c) * (c - a) == 0 or a + b + c != 6) {
            color = false;
        }
        next[v] = w, prev[w] = v;
        deg[v] -= 1, deg[w] -= 1;
        if (deg[v] == 2) {
            que.push(v);
        }
        if (deg[w] == 2) {
            que.push(w);
        }
    }
    if (!triangle) {
        std::cout << "neispravna triangulacija\n";
    } else if (!color) {
        std::cout << "neispravno bojenje\n";
    } else {
        std::cout << "tocno\n";
    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 23 / 23
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35