제출 #222395

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
222395		lyc	Checker (COCI19_checker)	C++14	110 / 110	702 ms	36196 KiB

checker

#include <bits/stdc++.h>
using namespace std;

#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int MX_N = 2e5+5;
using ii = pair<int,int>;

int ST;

int N;
int deg[MX_N];
set<ii> hull;
map<ii,int> edges;
queue<set<ii>::iterator> q;

bool check(set<ii>::iterator it) {
    if (deg[it->first] != 2) return false;
    //cout << "CHECKING " << it->first << " " << it->second << endl;
    auto prv = (it == hull.begin() ? prev(hull.end()) : prev(it));
    auto nxt = (next(it) == hull.end() ? hull.begin() : next(it));
    ii e = ii(prv->first, nxt->first);
    //cout << "\t edge " << e.first << " " << e.second << endl;
    if (e.first > e.second) swap(e.first, e.second);
    //cout << "\t good? " << edges.count(e) << endl;
    return edges.count(e);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> ST;

    cin >> N;
    FOR(i,1,N){
        char C; cin >> C;
        edges[ii(i,i+1)] = C;
        hull.insert(ii(i,C-'0'));
        deg[i] = 2;
    }
    FOR(i,1,N-3){
        int X, Y, C; cin >> X >> Y >> C;
        if (X > Y) swap(X,Y);
        edges[ii(X,Y)] = C;
        ++deg[X];
        ++deg[Y];
    }

    //set<ii>::iterator P = hull.end();
    for (auto it = hull.begin(); it != hull.end(); ++it) {
        //cout << "TRY " << it->first << " " << it->second << endl;
        if (check(it)) {
            //P = it;
            q.push(it);
        }
    }

    bool isPat = true;
    while (!q.empty() && SZ(hull) > 2) {
        auto P = q.front(); q.pop();
        auto prv = (P == hull.begin() ? prev(hull.end()) : prev(P));
        auto nxt = (next(P) == hull.end() ? hull.begin() : next(P));

        ii e = ii(prv->first, nxt->first);
        if (e.first > e.second) swap(e.first, e.second);
        //cout << "HULL IS NOW " << SZ(hull) << " :: P " << P->first << " " << P->second << " :: E " << e.first << " " << e.second << endl;
        int a = prv->second, b = P->second, c = edges[e];
        isPat &= (a != b && a != c && b != c);

        hull.erase(P);
        --deg[e.first];
        --deg[e.second];

        ii nw = ii(prv->first, c);
        hull.erase(prv);
        hull.insert(nw);

        //for (auto& x : hull) cout << x.first << " " << x.second << " || ";
        //cout << endl;

        if (check(nxt)) q.push(nxt);
        if (check(prev(nxt))) q.push(prev(nxt));
    }

    if (SZ(hull) != 2) {
        cout << "neispravna triangulacija" << '\n';
    } else if (!isPat) {
        cout << "neispravno bojenje" << '\n';
    } else {
        cout << "tocno" << '\n';
    }
}

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