Submission #222447

#TimeUsernameProblemLanguageResultExecution timeMemory
222447cheehengChecker (COCI19_checker)C++14
52 / 110
292 ms84580 KiB
#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 (stderr)

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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...