oj.uz

Submission #222470

# Submission time Handle Problem Language Result Execution time Memory
222470 2020-04-13T08:01:26 Z cheeheng Checker (COCI19_checker) C++14
52 / 110
 538 ms 136932 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 55288 KB Output is correct
2 Correct 35 ms 55288 KB Output is correct
3 Correct 34 ms 55296 KB Output is correct
4 Correct 34 ms 55296 KB Output is correct
5 Correct 40 ms 55424 KB Output is correct
6 Correct 34 ms 55292 KB Output is correct
7 Correct 34 ms 55288 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 55288 KB Output is correct
2 Correct 35 ms 55288 KB Output is correct
3 Correct 34 ms 55296 KB Output is correct
4 Correct 34 ms 55296 KB Output is correct
5 Correct 40 ms 55424 KB Output is correct
6 Correct 34 ms 55292 KB Output is correct
7 Correct 34 ms 55288 KB Output is correct
8 Correct 37 ms 56184 KB Output is correct
9 Correct 37 ms 56184 KB Output is correct
10 Correct 37 ms 56064 KB Output is correct
11 Correct 37 ms 56056 KB Output is correct
12 Correct 36 ms 56184 KB Output is correct
13 Correct 38 ms 56192 KB Output is correct
14 Correct 36 ms 56184 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 136804 KB Output is correct
2 Correct 514 ms 136804 KB Output is correct
3 Correct 499 ms 136932 KB Output is correct
4 Correct 492 ms 136812 KB Output is correct
5 Correct 490 ms 136804 KB Output is correct
6 Correct 538 ms 134500 KB Output is correct
7 Correct 524 ms 134500 KB Output is correct
8 Correct 531 ms 134464 KB Output is correct
9 Correct 521 ms 134628 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 251 ms 113912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 55288 KB Output is correct
2 Correct 35 ms 55288 KB Output is correct
3 Correct 34 ms 55296 KB Output is correct
4 Correct 34 ms 55296 KB Output is correct
5 Correct 40 ms 55424 KB Output is correct
6 Correct 34 ms 55292 KB Output is correct
7 Correct 34 ms 55288 KB Output is correct
8 Correct 37 ms 56184 KB Output is correct
9 Correct 37 ms 56184 KB Output is correct
10 Correct 37 ms 56064 KB Output is correct
11 Correct 37 ms 56056 KB Output is correct
12 Correct 36 ms 56184 KB Output is correct
13 Correct 38 ms 56192 KB Output is correct
14 Correct 36 ms 56184 KB Output is correct
15 Correct 516 ms 136804 KB Output is correct
16 Correct 514 ms 136804 KB Output is correct
17 Correct 499 ms 136932 KB Output is correct
18 Correct 492 ms 136812 KB Output is correct
19 Correct 490 ms 136804 KB Output is correct
20 Correct 538 ms 134500 KB Output is correct
21 Correct 524 ms 134500 KB Output is correct
22 Correct 531 ms 134464 KB Output is correct
23 Correct 521 ms 134628 KB Output is correct
24 Runtime error 251 ms 113912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -