Submission #222471

#	Time	Username	Problem	Language	Result	Execution time	Memory
222471		cheeheng	Checker (COCI19_checker)	C++14	110 / 110	707 ms	146644 KiB

checker

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

#define all(x) (x).begin(), (x).end()

typedef pair<int, int> ii;

map<int, int> colour1[300005];

char colour[200005];

int deg[200005];

int X[200005];
int Y[200005];

vector<int> AdjList[200005];

int AdjMat[3005][3005];

int A[200005][20];
int B[200005][20];
int log_2[200005];

int N;

void init(){
    log_2[1] = 0;
    for(int i = 1; i <= 200000; i ++){
        log_2[i] = log_2[i/2]+1;
    }
    for(int k = 1; k <= 19; k ++){
        for(int i = 0; i+(1<<(k-1)) <= N; i ++){
            A[i][k] = min(A[i][k-1], A[i+(1<<(k-1))][k-1]);
            B[i][k] = max(B[i][k-1], B[i+(1<<(k-1))][k-1]);
        }
    }
}

/*int rminq(int i, int j){
    int log2r = log2[j-i+1];
    return min(A[i][log2r], A[j-(1<<log2r)+1][log2r]);
}*/

int rmaxq(int i, int j){
    int log2r = log_2[j-i+1];
    return max(B[i][log2r], B[j-(1<<log2r)+1][log2r]);
}


int main(){
    int ST;
    scanf("%d", &ST);

    scanf("%d", &N);

    scanf(" %s", colour);

    memset(AdjMat, 0, sizeof(AdjMat));
    memset(deg, 0, sizeof(deg));
    for(int i = 0; i < N; i ++){
        AdjList[i+1].push_back( ((i+1)%N)+1 );
        deg[i+1] ++;
        deg[((i+1)%N)+1] ++;

        colour1[i+1][((i+1)%N)+1] = colour[i]-'0';
        colour1[((i+1)%N)+1][i+1] = colour[i]-'0';

        //printf("%d %d\n", i+1, ((i+1)%N)+1);

        AdjList[((i+1)%N)+1].push_back( i+1 );

        if(ST < 3){
            AdjMat[((i+1)%N)+1][i+1] = colour[i]-'0';
            AdjMat[i+1][((i+1)%N)+1] = colour[i]-'0';
        }
    }

    vector<ii> edges;
    for(int i = 0; i < N-3; i ++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);

        X[i] = min(a, b);
        Y[i] = max(a, b);
        deg[a] ++;
        deg[b] ++;
        edges.push_back(ii(X[i], Y[i]));
        colour1[a][b] = c;
        colour1[b][a] = c;
        if(ST <= 2){
            AdjMat[a][b] = AdjMat[b][a] = c;
        }
        AdjList[a].push_back(b);
        AdjList[b].push_back(a);
    }
    sort(all(edges));

    for(int i = 0; i < N-3; i ++){
        A[i][0] = B[i][0] = edges[i].second;
    }

    for(int i = 0; i < N-3; i ++){
        int X, Y;
        tie(X, Y) = edges[i];
        //printf("Edge: %d %d\n", X, Y);
        int indx_min = lower_bound(all(edges), ii(X+1, -1))-edges.begin();
        int indx_max = lower_bound(all(edges), ii(Y, -1))-edges.begin();
        if(indx_min == indx_max){
            continue;
        }

        int temp_max = rmaxq(indx_min, indx_max-1);
        if(temp_max > Y){
            printf("neispravna triangulacija\n");
            return 0;
        }
    }

    if(ST == 3){printf("tocno"); return 0;}

    set<int> s;
    queue<int> q;
    for(int i = 1; i <= N; i ++){
        s.insert(i);
        //printf("%d %d\n", i, deg[i]);
        if(deg[i] == 2){
            q.push(i);
        }
    }

    while(s.size() >= 3){
        int y = q.front(); q.pop();
        auto it = s.find(y);

        int x, z;
        if(y == *s.begin()){
            x = *(--s.end());
        }else{
            it --;
            x = *it;
            it ++;
        }

        if(y == *(--s.end())){
            z = *s.begin();
        }else{
            it ++;
            z = *it;
            it --;
        }

        //printf("Triangle: %d %d %d\n", x, y, z);

        if( ((1<<(2*colour1[x][y]))+(1<<(2*colour1[y][z]))+(1<<(2*colour1[x][z]))) != 64+16+4){
            printf("neispravno bojenje");
            return 0;
        }

        deg[y] = 0;
        s.erase(y);
        deg[x] --;
        deg[z] --;
        if(deg[x] == 2){
            q.push(x);
        }
        if(deg[z] == 2){
            q.push(z);
        }
    }

    /*for(int i = 1; i <= N; i ++){
        for(int j: AdjList[i]){
            //printf("AdjList: %d %d\n", i, j);
            for(int k: AdjList[j]){
                if(i == k){continue;}
                //printf("324: %d %d %d\n", i, j, k);
                if(AdjMat[i][k]){
                    if( ((1<<AdjMat[i][k]) + (1<<AdjMat[i][j]) + (1<<AdjMat[j][k])) != 14){
                        //printf("%d%d%d\n", AdjMat[i][k], AdjMat[i][j], AdjMat[j][k]);
                        printf("neispravno bojenje");
                        return 0;
                    }
                }
            }
        }
    }*/

    printf("tocno");
    return 0;
}

Compilation message (stderr)

checker.cpp: In function 'int main()':
checker.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &ST);
     ~~~~~^~~~~~~~~~~
checker.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
checker.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", colour);
     ~~~~~^~~~~~~~~~~~~~~
checker.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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