oj.uz

Submission #1101286

# Submission time Handle Problem Language Result Execution time Memory
1101286 2024-10-16T03:42:00 Z vjudge1 Checker (COCI19_checker) C++17
110 / 110
 794 ms 68048 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()
#define EQUAL 0
#define SMALLER 1
#define SMALLER_OR_EQUAL 2
#define LARGER -1
#define LARGER_OR_EQUAL -2
#define UNKNOWN 7
#define UNDEFINED -7
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() {
    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() {
    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:89: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]
   89 |     if (f.size() != 4 * N - 6)
      |         ~~~~~~~~~^~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 6 ms 5160 KB Output is correct
4 Correct 5 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 5 ms 5160 KB Output is correct
7 Correct 4 ms 5156 KB Output is correct
8 Correct 7 ms 5716 KB Output is correct
9 Correct 9 ms 5652 KB Output is correct
10 Correct 6 ms 5716 KB Output is correct
11 Correct 5 ms 5716 KB Output is correct
12 Correct 7 ms 5716 KB Output is correct
13 Correct 8 ms 5716 KB Output is correct
14 Correct 6 ms 5716 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 67888 KB Output is correct
2 Correct 746 ms 67804 KB Output is correct
3 Correct 508 ms 67800 KB Output is correct
4 Correct 456 ms 67800 KB Output is correct
5 Correct 498 ms 67932 KB Output is correct
6 Correct 748 ms 65992 KB Output is correct
7 Correct 763 ms 65908 KB Output is correct
8 Correct 527 ms 65480 KB Output is correct
9 Correct 532 ms 65480 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 67772 KB Output is correct
2 Correct 651 ms 67800 KB Output is correct
3 Correct 645 ms 67752 KB Output is correct
4 Correct 482 ms 67764 KB Output is correct
5 Correct 462 ms 67696 KB Output is correct
6 Correct 743 ms 66388 KB Output is correct
7 Correct 794 ms 66092 KB Output is correct
8 Correct 538 ms 65992 KB Output is correct
9 Correct 494 ms 65956 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 6 ms 5160 KB Output is correct
4 Correct 5 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 5 ms 5160 KB Output is correct
7 Correct 4 ms 5156 KB Output is correct
8 Correct 7 ms 5716 KB Output is correct
9 Correct 9 ms 5652 KB Output is correct
10 Correct 6 ms 5716 KB Output is correct
11 Correct 5 ms 5716 KB Output is correct
12 Correct 7 ms 5716 KB Output is correct
13 Correct 8 ms 5716 KB Output is correct
14 Correct 6 ms 5716 KB Output is correct
15 Correct 777 ms 67888 KB Output is correct
16 Correct 746 ms 67804 KB Output is correct
17 Correct 508 ms 67800 KB Output is correct
18 Correct 456 ms 67800 KB Output is correct
19 Correct 498 ms 67932 KB Output is correct
20 Correct 748 ms 65992 KB Output is correct
21 Correct 763 ms 65908 KB Output is correct
22 Correct 527 ms 65480 KB Output is correct
23 Correct 532 ms 65480 KB Output is correct
24 Correct 713 ms 67772 KB Output is correct
25 Correct 651 ms 67800 KB Output is correct
26 Correct 645 ms 67752 KB Output is correct
27 Correct 482 ms 67764 KB Output is correct
28 Correct 462 ms 67696 KB Output is correct
29 Correct 743 ms 66388 KB Output is correct
30 Correct 794 ms 66092 KB Output is correct
31 Correct 538 ms 65992 KB Output is correct
32 Correct 494 ms 65956 KB Output is correct
33 Correct 716 ms 68048 KB Output is correct
34 Correct 735 ms 67740 KB Output is correct
35 Correct 481 ms 67944 KB Output is correct
36 Correct 491 ms 67796 KB Output is correct
37 Correct 497 ms 67804 KB Output is correct
38 Correct 506 ms 67748 KB Output is correct
39 Correct 522 ms 67804 KB Output is correct
40 Correct 736 ms 66032 KB Output is correct
41 Correct 758 ms 66244 KB Output is correct
42 Correct 504 ms 65676 KB Output is correct
43 Correct 568 ms 66116 KB Output is correct