oj.uz

Submission #633971

# Submission time Handle Problem Language Result Execution time Memory
633971 2022-08-23T14:41:07 Z Olympia Checker (COCI19_checker) C++17
110 / 110
 1205 ms 91460 KB 
#include <bits/stdc++.h>


using namespace std;

void triangulation (vector<pair<int,int> > vec, int n) {
    vector<int> adj[n];
    set<int> s[n];
    for (auto& p: vec) {
        adj[p.first].push_back(p.second), s[p.first].insert(p.second);
        adj[p.second].push_back(p.first), s[p.second].insert(p.first);
    }
    for (int i = 0; i < n; i++) {
        for (int j: adj[i]) {
            if (adj[j].size() < adj[i].size()) {
                for (int x: adj[j]) {
                    if (s[i].count(x)) {
                        cout << "neispravno bojenje";
                        exit(0);
                    }
                }
            } else {
                for (int x: adj[i]) {
                    if (s[j].count(x)) {
                        cout << "neispravno bojenje";
                        exit(0);
                    }
                }
            }
        }
    }
}

vector<pair<int,int> > merge (vector<pair<int,int> > v1, vector<pair<int,int> > v2) {
    for (auto& p: v2) {
        v1.push_back(p);
    }
    return v1;
}

int main () {
    int t, n;
    cin >> t >> n;
    string str;
    cin >> str;
    vector<pair<int,int> > color[3];
    for (int i = 0; i < str.size(); i++) {
        color[str[i] - '1'].push_back(make_pair(i, (i + 1) % n));
    }
    vector<pair<pair<int,int>,int> > vec(n - 3);
    set<int> st[n];
    for (int i = 0; i < n - 3; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        c--;
        x--, y--;
        if (x > y) {
            swap(x, y);
        }
        color[c].push_back(make_pair(x, y));
        vec.push_back(make_pair(make_pair(x, y), c));
        st[x].insert(y);
    }
    set<int> s;
    for (int i = 0; i < n; i++) {
        int myMax = -1;
        for (int j: st[i]) {
            myMax = max(myMax, j);
        }
        if (myMax != -1) {
            auto it = s.upper_bound(i);
            if (it != s.end() && *it < myMax) {
                cout << "neispravna triangulacija\n";
                exit(0);
            }
        }
        for (int j: st[i]) {
            s.insert(j);
        }
    }
    triangulation(merge(color[0], color[1]), n);
    triangulation(merge(color[2], color[1]), n);
    triangulation(merge(color[0], color[2]), n);
    cout << "tocno\n";
}

Compilation message

checker.cpp: In function 'int main()':
checker.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < str.size(); i++) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 5 ms 1108 KB Output is correct
9 Correct 5 ms 1136 KB Output is correct
10 Correct 2 ms 568 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 4 ms 1016 KB Output is correct
13 Correct 4 ms 1064 KB Output is correct
14 Correct 3 ms 1108 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1040 ms 86196 KB Output is correct
2 Correct 1006 ms 86248 KB Output is correct
3 Correct 202 ms 30824 KB Output is correct
4 Correct 201 ms 30864 KB Output is correct
5 Correct 191 ms 30872 KB Output is correct
6 Correct 1092 ms 83088 KB Output is correct
7 Correct 1140 ms 91460 KB Output is correct
8 Correct 200 ms 30304 KB Output is correct
9 Correct 209 ms 30244 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1072 ms 84240 KB Output is correct
2 Correct 1010 ms 86248 KB Output is correct
3 Correct 409 ms 84204 KB Output is correct
4 Correct 393 ms 84188 KB Output is correct
5 Correct 386 ms 84212 KB Output is correct
6 Correct 1146 ms 86564 KB Output is correct
7 Correct 1205 ms 89692 KB Output is correct
8 Correct 628 ms 83108 KB Output is correct
9 Correct 435 ms 90796 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 5 ms 1108 KB Output is correct
9 Correct 5 ms 1136 KB Output is correct
10 Correct 2 ms 568 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 4 ms 1016 KB Output is correct
13 Correct 4 ms 1064 KB Output is correct
14 Correct 3 ms 1108 KB Output is correct
15 Correct 1040 ms 86196 KB Output is correct
16 Correct 1006 ms 86248 KB Output is correct
17 Correct 202 ms 30824 KB Output is correct
18 Correct 201 ms 30864 KB Output is correct
19 Correct 191 ms 30872 KB Output is correct
20 Correct 1092 ms 83088 KB Output is correct
21 Correct 1140 ms 91460 KB Output is correct
22 Correct 200 ms 30304 KB Output is correct
23 Correct 209 ms 30244 KB Output is correct
24 Correct 1072 ms 84240 KB Output is correct
25 Correct 1010 ms 86248 KB Output is correct
26 Correct 409 ms 84204 KB Output is correct
27 Correct 393 ms 84188 KB Output is correct
28 Correct 386 ms 84212 KB Output is correct
29 Correct 1146 ms 86564 KB Output is correct
30 Correct 1205 ms 89692 KB Output is correct
31 Correct 628 ms 83108 KB Output is correct
32 Correct 435 ms 90796 KB Output is correct
33 Correct 1063 ms 86164 KB Output is correct
34 Correct 1039 ms 86224 KB Output is correct
35 Correct 210 ms 31080 KB Output is correct
36 Correct 216 ms 30836 KB Output is correct
37 Correct 611 ms 84328 KB Output is correct
38 Correct 688 ms 86296 KB Output is correct
39 Correct 413 ms 84120 KB Output is correct
40 Correct 1156 ms 83588 KB Output is correct
41 Correct 1171 ms 89064 KB Output is correct
42 Correct 196 ms 30244 KB Output is correct
43 Correct 668 ms 83364 KB Output is correct