Submission #1101294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101294		nguyen31hoang08minh2003	Checker (COCI19_checker)	C++14	110 / 110	738 ms	67880 KiB

checker

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#include <numeric>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <strings.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

constexpr int MAX_N = 2E5 + 5;

int N, T;
string c;
vector<int> g[MAX_N];
map<pair<int, int>, int> f;

bool isInOrder(const int l, const int m, const int r) {
    if (l < r)
        return l <= m && m <= r;
    if (l > r)
        return l <= m || m <= r;
    return l == m;
}

int getNext(const int x) {
    return x == N ? 1 : (x + 1);
}

int getPrevious(const int x) {
    return x == 1 ? N : (x - 1);
}

void addSide(const int x, const int y, const int c) {
    g[x].push_back(y);
    g[y].push_back(x);
    f[make_pair(x, y)] = f[make_pair(y, x)] = c;
}

bool checkTriangulation() {
    /**

        Choose any diagonal and split the polygon
            then there should be no diagonal from one of two new polygons
                that go outside

        Implementation
            Iterate from 1 to N
                and consider sides
                    if the index of vertex is smaller than the current one then
                        it is one of the edges considered earlier and
                            there is no need to consider it in this and later iterations
                        therefore we can ignore it
                    otherwise
                        it is one of new boundary (the diagonal along which we have to cut)
                            that we must consider

            To store the currently considered boundaries, we can use stack (last-in first-out)
                as the boundaries we start considering later should be removed/ignored earlier

    **/

    if (f.size() != 4 * N - 6)
        return false;

    stack<int> p;

    fort(x, 1, N) {
        ford(i, sz(g[x]) - 1, 0) {
            const int &y = g[x][i];
            if (y < x) {
                p.pop();
                continue;
            }
            if (!p.empty() && p.top() < y)
                return false;
            p.push(y);
        }
    }

    return true;
}

bool checkPatriotic() {
    /**

        Sort the adjacent vertices
            and check the color

    **/

    fort(x, 1, N)
        fore(i, 1, sz(g[x])) {
            const int   &y = g[x][i],
                        &z = g[x][i - 1],
                        &a = f[make_pair(x, y)],
                        &b = f[make_pair(x, z)],
                        &c = f[make_pair(y, z)];
            if (a == b || b == c || a == c)
                return false;
        }

    return true;
}

signed main() {

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> T >> N >> c;

    fort(x, 1, N)
        addSide(x, getNext(x), c[x - 1] - '0');

    for (int e = N - 3, X, Y, C; e > 0; --e) {
        cin >> X >> Y >> C;
        addSide(X, Y, C);
    }

    fort(x, 1, N)
        sort(all(g[x]), [&](const int &l, const int &r) -> bool {
            const bool u = (x < l), v = (x < r);
            if (u != v)
                return u;
            return l < r;
        });

    if (!checkTriangulation()) {
        puts("neispravna triangulacija");
        return 0;
    }

    if (!checkPatriotic()) {
        puts("neispravno bojenje");
        return 0;
    }

    puts("tocno");

    return 0;
}

Compilation message (stderr)

checker.cpp: In function 'bool checkTriangulation()':
checker.cpp:104:18: warning: comparison of integer expressions of different signedness: 'std::map<std::pair<int, int>, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |     if (f.size() != 4 * N - 6)
      |         ~~~~~~~~~^~~~~~~~~~~~

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