oj.uz

Submission #222391

# Submission time Handle Problem Language Result Execution time Memory
222391 2020-04-13T06:19:56 Z dwsc Checker (COCI19_checker) C++14
110 / 110
 847 ms 32832 KB 
#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.0 / 12.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 32776 KB Output is correct
2 Correct 816 ms 32776 KB Output is correct
3 Correct 731 ms 32776 KB Output is correct
4 Correct 563 ms 32648 KB Output is correct
5 Correct 556 ms 32776 KB Output is correct
6 Correct 523 ms 32648 KB Output is correct
7 Correct 543 ms 32648 KB Output is correct
8 Correct 449 ms 32776 KB Output is correct
9 Correct 455 ms 32648 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 32752 KB Output is correct
2 Correct 814 ms 32648 KB Output is correct
3 Correct 821 ms 32776 KB Output is correct
4 Correct 808 ms 32776 KB Output is correct
5 Correct 818 ms 32696 KB Output is correct
6 Correct 523 ms 32648 KB Output is correct
7 Correct 533 ms 32556 KB Output is correct
8 Correct 520 ms 32776 KB Output is correct
9 Correct 539 ms 32652 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 8 ms 640 KB Output is correct
9 Correct 8 ms 640 KB Output is correct
10 Correct 8 ms 640 KB Output is correct
11 Correct 8 ms 640 KB Output is correct
12 Correct 9 ms 640 KB Output is correct
13 Correct 8 ms 640 KB Output is correct
14 Correct 8 ms 640 KB Output is correct
15 Correct 847 ms 32776 KB Output is correct
16 Correct 816 ms 32776 KB Output is correct
17 Correct 731 ms 32776 KB Output is correct
18 Correct 563 ms 32648 KB Output is correct
19 Correct 556 ms 32776 KB Output is correct
20 Correct 523 ms 32648 KB Output is correct
21 Correct 543 ms 32648 KB Output is correct
22 Correct 449 ms 32776 KB Output is correct
23 Correct 455 ms 32648 KB Output is correct
24 Correct 819 ms 32752 KB Output is correct
25 Correct 814 ms 32648 KB Output is correct
26 Correct 821 ms 32776 KB Output is correct
27 Correct 808 ms 32776 KB Output is correct
28 Correct 818 ms 32696 KB Output is correct
29 Correct 523 ms 32648 KB Output is correct
30 Correct 533 ms 32556 KB Output is correct
31 Correct 520 ms 32776 KB Output is correct
32 Correct 539 ms 32652 KB Output is correct
33 Correct 815 ms 32652 KB Output is correct
34 Correct 813 ms 32832 KB Output is correct
35 Correct 789 ms 32664 KB Output is correct
36 Correct 568 ms 32808 KB Output is correct
37 Correct 804 ms 32776 KB Output is correct
38 Correct 820 ms 32588 KB Output is correct
39 Correct 823 ms 32776 KB Output is correct
40 Correct 510 ms 32648 KB Output is correct
41 Correct 543 ms 32776 KB Output is correct
42 Correct 456 ms 32648 KB Output is correct
43 Correct 503 ms 32648 KB Output is correct