This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |