Submission #495979

#	Time	Username	Problem	Language	Result	Execution time	Memory
495979		AlperenT	Checker (COCI19_checker)	C++17	110 / 110	348 ms	30540 KiB

checker

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int t, n, a, b, c, lg2[N];

string str;

vector<pair<int, int>> graph[N];

vector<array<int, 3>> edges;

priority_queue<int, vector<int>, greater<int>> pq;

bool flag1 = true, flag2 = true;

bool check(int nodea, int nodeb, int c){
    vector<pair<int, int>> v, &va = graph[nodea], &vb = graph[nodeb];

    bool flag = false;
    if(vb.size() < va.size()) flag = true, swap(va, vb);

    if(va.size() * (lg2[vb.size()] + 1) < va.size() + vb.size()){;
        for(auto p : va){
            auto it = lower_bound(vb.begin(), vb.end(), pair{p.first, 0});

            if(it != vb.end()){
                pair<int, int> p2 = *it;

                if(p.first == p2.first) v.push_back({p.second, p2.second});
            }
        }
    }
    else{
        int a = 0, b = 0;

        while(a < va.size() && b < vb.size()){
            if(va[a].first == vb[b].first){
                v.push_back({va[a].second, vb[b].second});
                a++, b++;
            }
            else if(va[a].first < vb[b].first) a++;
            else if(vb[b].first < va[a].first) b++;
        }
    }

    if(flag) swap(va, vb);

    for(auto p : v){
        if(p.first != p.second && p.first != c && p.second != c) continue;
        else return false;
    }

    return true;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    for(int i = 2; i < N; i++) lg2[i] = lg2[i / 2] + 1;

    cin >> t >> n;

    cin >> str;

    str = '$' + str;

    for(int i = 1; i <= n - 1; i++){
        edges.push_back({i, i + 1, str[i] - '0'});
        edges.push_back({i + 1, i, str[i] - '0'});
    }

    edges.push_back({n, 1, str[n] - '0'});
    edges.push_back({1, n, str[n] - '0'});

    for(int i = 1; i <= n - 3; i++){
        cin >> a >> b >> c;

        if(b < a) swap(a, b);

        graph[a].push_back({b, c});
        edges.push_back({b, a, c});
    }

    for(int v = 1; v <= n; v++){
        while(!pq.empty() && pq.top() <= v) pq.pop();

        for(auto e : graph[v]) if(!pq.empty() && e.first > pq.top()) flag1 = false;

        for(auto e : graph[v]) pq.push(e.first);
    }

    if(flag1){
        for(auto e : edges) graph[e[0]].push_back({e[1], e[2]});

        for(int v = 1; v <= n; v++) sort(graph[v].begin(), graph[v].end());

        for(int v = 1; v <= n; v++){
            for(auto e : graph[v]){
                if(!check(v, e.first, e.second)) flag2 = false;
            }
        }
    }

    if(!flag1) cout << "neispravna triangulacija";
    else{
        if(!flag2) cout << "neispravno bojenje";
        else cout << "tocno";
    }
}

Compilation message (stderr)

checker.cpp: In function 'bool check(int, int, int)':
checker.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         while(a < va.size() && b < vb.size()){
      |               ~~^~~~~~~~~~~
checker.cpp:39:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         while(a < va.size() && b < vb.size()){
      |                                ~~^~~~~~~~~~~

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