oj.uz

Submission #222447

# Submission time Handle Problem Language Result Execution time Memory
222447 2020-04-13T07:28:29 Z cheeheng Checker (COCI19_checker) C++14
52 / 110
 292 ms 84580 KB 
#include <bits/stdc++.h>
using namespace std;

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

typedef pair<int, int> ii;

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));
    for(int i = 0; i < N; i ++){
        AdjList[i+1].push_back( ((i+1)%N)+1 );

        //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';
        }
    }

    memset(deg, 0, sizeof(deg));
    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);
        edges.push_back(ii(X[i], Y[i]));
        if(ST != 3){
            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;
        }
    }

    /*for(int i = 0; i < N-3; i ++){
        for(int j = 0; j < N-3; j ++){
            if(i == j){continue;}
            if(X[i] < X[j] && X[j] < Y[i] && Y[i] < Y[j]){
                printf("neispravna triangulacija");
                return 0;
            }

            if(X[j] < Y[i] && Y[i] < Y[j] && Y[j] < X[i]){
                printf("neispravna triangulacija");
                return 0;
            }

            if(Y[i] < Y[j] && Y[j] < X[i] && X[i] < X[j]){
                printf("neispravna triangulacija");
                return 0;
            }

            if(Y[j] < X[i] && X[i] < X[j] && X[j] < Y[i]){
                printf("neispravna triangulacija");
                return 0;
            }
        }
    }*/

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

    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:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &ST);
     ~~~~~^~~~~~~~~~~
checker.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
checker.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", colour);
     ~~~~~^~~~~~~~~~~~~~~
checker.cpp:75: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 28 ms 41216 KB Output is correct
2 Correct 27 ms 41344 KB Output is correct
3 Correct 33 ms 41216 KB Output is correct
4 Correct 29 ms 41216 KB Output is correct
5 Correct 31 ms 41208 KB Output is correct
6 Correct 27 ms 41216 KB Output is correct
7 Correct 27 ms 41216 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 41216 KB Output is correct
2 Correct 27 ms 41344 KB Output is correct
3 Correct 33 ms 41216 KB Output is correct
4 Correct 29 ms 41216 KB Output is correct
5 Correct 31 ms 41208 KB Output is correct
6 Correct 27 ms 41216 KB Output is correct
7 Correct 27 ms 41216 KB Output is correct
8 Correct 29 ms 41600 KB Output is correct
9 Correct 36 ms 41600 KB Output is correct
10 Correct 30 ms 41768 KB Output is correct
11 Correct 36 ms 41600 KB Output is correct
12 Correct 32 ms 41600 KB Output is correct
13 Correct 29 ms 41600 KB Output is correct
14 Correct 28 ms 41600 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 84452 KB Output is correct
2 Correct 292 ms 84580 KB Output is correct
3 Correct 259 ms 84536 KB Output is correct
4 Correct 282 ms 84500 KB Output is correct
5 Correct 262 ms 84508 KB Output is correct
6 Correct 250 ms 83532 KB Output is correct
7 Correct 241 ms 83464 KB Output is correct
8 Correct 224 ms 83556 KB Output is correct
9 Correct 212 ms 83404 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 229 ms 83064 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 28 ms 41216 KB Output is correct
2 Correct 27 ms 41344 KB Output is correct
3 Correct 33 ms 41216 KB Output is correct
4 Correct 29 ms 41216 KB Output is correct
5 Correct 31 ms 41208 KB Output is correct
6 Correct 27 ms 41216 KB Output is correct
7 Correct 27 ms 41216 KB Output is correct
8 Correct 29 ms 41600 KB Output is correct
9 Correct 36 ms 41600 KB Output is correct
10 Correct 30 ms 41768 KB Output is correct
11 Correct 36 ms 41600 KB Output is correct
12 Correct 32 ms 41600 KB Output is correct
13 Correct 29 ms 41600 KB Output is correct
14 Correct 28 ms 41600 KB Output is correct
15 Correct 281 ms 84452 KB Output is correct
16 Correct 292 ms 84580 KB Output is correct
17 Correct 259 ms 84536 KB Output is correct
18 Correct 282 ms 84500 KB Output is correct
19 Correct 262 ms 84508 KB Output is correct
20 Correct 250 ms 83532 KB Output is correct
21 Correct 241 ms 83464 KB Output is correct
22 Correct 224 ms 83556 KB Output is correct
23 Correct 212 ms 83404 KB Output is correct
24 Runtime error 229 ms 83064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -