oj.uz

Submission #1101294

# Submission time Handle Problem Language Result Execution time Memory
1101294 2024-10-16T03:50:02 Z nguyen31hoang08minh2003 Checker (COCI19_checker) C++14
110 / 110
 738 ms 67880 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 2 ms 4944 KB Output is correct
7 Correct 2 ms 4944 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 2 ms 4944 KB Output is correct
7 Correct 2 ms 4944 KB Output is correct
8 Correct 5 ms 5712 KB Output is correct
9 Correct 5 ms 5712 KB Output is correct
10 Correct 4 ms 5712 KB Output is correct
11 Correct 4 ms 5712 KB Output is correct
12 Correct 4 ms 5712 KB Output is correct
13 Correct 4 ms 5712 KB Output is correct
14 Correct 4 ms 5544 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 67812 KB Output is correct
2 Correct 670 ms 64724 KB Output is correct
3 Correct 444 ms 66396 KB Output is correct
4 Correct 438 ms 67716 KB Output is correct
5 Correct 502 ms 67740 KB Output is correct
6 Correct 736 ms 62676 KB Output is correct
7 Correct 715 ms 65980 KB Output is correct
8 Correct 484 ms 64452 KB Output is correct
9 Correct 485 ms 62432 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 736 ms 64844 KB Output is correct
2 Correct 705 ms 66516 KB Output is correct
3 Correct 610 ms 67880 KB Output is correct
4 Correct 556 ms 64724 KB Output is correct
5 Correct 524 ms 64660 KB Output is correct
6 Correct 713 ms 63156 KB Output is correct
7 Correct 738 ms 66276 KB Output is correct
8 Correct 536 ms 63172 KB Output is correct
9 Correct 517 ms 65988 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 2 ms 4944 KB Output is correct
7 Correct 2 ms 4944 KB Output is correct
8 Correct 5 ms 5712 KB Output is correct
9 Correct 5 ms 5712 KB Output is correct
10 Correct 4 ms 5712 KB Output is correct
11 Correct 4 ms 5712 KB Output is correct
12 Correct 4 ms 5712 KB Output is correct
13 Correct 4 ms 5712 KB Output is correct
14 Correct 4 ms 5544 KB Output is correct
15 Correct 651 ms 67812 KB Output is correct
16 Correct 670 ms 64724 KB Output is correct
17 Correct 444 ms 66396 KB Output is correct
18 Correct 438 ms 67716 KB Output is correct
19 Correct 502 ms 67740 KB Output is correct
20 Correct 736 ms 62676 KB Output is correct
21 Correct 715 ms 65980 KB Output is correct
22 Correct 484 ms 64452 KB Output is correct
23 Correct 485 ms 62432 KB Output is correct
24 Correct 736 ms 64844 KB Output is correct
25 Correct 705 ms 66516 KB Output is correct
26 Correct 610 ms 67880 KB Output is correct
27 Correct 556 ms 64724 KB Output is correct
28 Correct 524 ms 64660 KB Output is correct
29 Correct 713 ms 63156 KB Output is correct
30 Correct 738 ms 66276 KB Output is correct
31 Correct 536 ms 63172 KB Output is correct
32 Correct 517 ms 65988 KB Output is correct
33 Correct 634 ms 66516 KB Output is correct
34 Correct 615 ms 66516 KB Output is correct
35 Correct 456 ms 64820 KB Output is correct
36 Correct 450 ms 66552 KB Output is correct
37 Correct 499 ms 66452 KB Output is correct
38 Correct 495 ms 67872 KB Output is correct
39 Correct 489 ms 64724 KB Output is correct
40 Correct 707 ms 62720 KB Output is correct
41 Correct 697 ms 63024 KB Output is correct
42 Correct 510 ms 62548 KB Output is correct
43 Correct 563 ms 62916 KB Output is correct