Submission #222391

#	Time	Username	Problem	Language	Result	Execution time	Memory
222391		dwsc	Checker (COCI19_checker)	C++14	110 / 110	847 ms	32832 KiB

checker

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
struct node{
    int next;
    int colour;
    node(int _next,int _colour){
        next = _next;
        colour = _colour;
    }
};
int n;
bool cmp(ii e1,ii e2){
    int dist1 = abs(e1.first-e1.second),dist2 = abs(e2.first-e2.second);
    dist1 = min(dist1,n-dist1);
    dist2 = min(dist2,n-dist2);
    return dist1 < dist2;
}
string invalid = "neispravna triangulacija";
string notpat = "neispravno bojenje";
string pat = "tocno";
int main(){
    int t;
    cin >> t;
    cin >> n;
    int colour[n];
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) colour[i] = s[i]-48;
    set<int> available;
    node* arr[n];
    for (int i = 0; i < n; i++){
        available.insert(i);
        arr[i] = new node((i+1)%n,colour[i]);
    }
    ii edge[n-3];
    map<ii,int> cmap;
    for (int i = 0; i < n-3; i++){
        cin >> edge[i].first >> edge[i].second;
        edge[i].first--;
        edge[i].second--;
        int c;
        cin >> c;
        cmap[edge[i]] = c;
    }
    int can = 1;
    sort(edge,edge+n-3,cmp);
    for (int i = 0; i < n-3; i++){
        int a = edge[i].first,b = edge[i].second;
        if (available.find(a) == available.end() || available.find(b) == available.end()){
            cout << invalid;
            return 0;
        }
        if (arr[arr[a]->next]->next == b){
            int c = arr[a]->next;
            int colour1 = cmap[edge[i]],colour2 = arr[a]->colour,colour3 = arr[c]->colour;
            if (colour1 == colour2 || colour1 == colour3 || colour2 == colour3) can = 0;
            available.erase(c);
            arr[a]->next = b;
            arr[a]->colour = colour1;
        }
        else if (arr[arr[b]->next]->next == a){
            int c = arr[b]->next;
            int colour1 = cmap[edge[i]],colour2 = arr[b]->colour,colour3 = arr[c]->colour;
            if (colour1 == colour2 || colour1 == colour3 || colour2 == colour3) can = 0;
            available.erase(c);
            arr[b]->next = a;
            arr[b]->colour = colour1;
        }
        else{
            cout << invalid;
            return 0;
        }
    }
    assert(available.size()==3);
    int a = *available.begin();
    int b = arr[a]->next;
    int c = arr[b]->next;
    assert(arr[c]->next == a);
    assert(available.find(b) != available.end());
    assert(available.find(c) != available.end());
    int colour1 = arr[a]->colour,colour2 = arr[b]->colour,colour3 = arr[c]->colour;
    if (colour1 == colour2 || colour1 == colour3 || colour2 == colour3) can = 0;
    if (can) cout << pat;
    else cout << notpat;
}

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