oj.uz

Submission #222507

# Submission time Handle Problem Language Result Execution time Memory
222507 2020-04-13T08:31:05 Z SomeoneUnknown Checker (COCI19_checker) C++14
0 / 110
 253 ms 18584 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
typedef pair<int, ii> iii; //from, to, col

ii mii(int a, int b){
    return make_pair(a,b);
}

iii miii(int a, int b, int c){
    return make_pair(a, mii(b,c));
}

vector<vector<ii> > adjlist;

int gcoloroflink(int f, int t){
    if(f >= t){
        exit(75);
    }
    int lo = -1;
    int hi = adjlist[f].size();
    while(hi-lo > 1){
        int mid = (lo+hi)/2;
        if(t == adjlist[f][mid].first){
            return adjlist[f][mid].second;
        }else if(t < adjlist[f][mid].first){
            hi = mid;
        }else{
            lo = mid;
        }
    }
    exit(76);
}

int main(){
    //printf("tocno");
    //return 0;
    int n;
    scanf("%d", &n);
    scanf("%d", &n);
    char c;
    scanf("%c", &c);
    int col;
    vector<ii> x;
    adjlist.push_back(x);
    for(int i = 1; i <= n; i++){
        vector<ii> x1;
        adjlist.push_back(x1);
        scanf("%c",&c);
        col = (int)(c-'0');
        if(i == n){
            adjlist[1].push_back(mii(n,col));
        }else{
            adjlist[i].push_back(mii(i+1,col));
        }
    }
    iii edges[n-3];
    for(int i = 0; i < n-3; i++){
        int f, t;
        scanf("%d %d %d", &f, &t, &col);
        if(t < f){
            int ph = f;
            f = t;
            t = ph;
        }
        edges[i] = miii(f,-t,col);
        adjlist[f].push_back(mii(t,col));
    }
    sort(edges,edges+n-3);
    stack<int> dne;
    dne.push(n+1);
    int prev = 0;
    for(int i = 0; i < n-3; i++){
        int to = -edges[i].second.first;
        if(to == dne.top() && prev == edges[i].first){
            printf("neispravna triangulacija");
            return 0;
        }
        while(dne.top() <= edges[i].first){
            dne.pop();
        }
        //printf("%d %d\n", to, dne.top());
        if(dne.top() < to){
            printf("neispravna triangulacija");
            return 0;
        }
        dne.push(to);
        prev = edges[i].first;
    }
    for(int i = 1; i <= n; i++){
        sort(adjlist[i].begin(), adjlist[i].end());
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j+1 < adjlist[i].size(); j++){
            printf("%d %d\n", i, adjlist[i][j].first);
            bool cused[4];
            for(int k = 1; k < 4; k++) cused[k] = false;
            cused[adjlist[i][j].second] = true;
            if(cused[adjlist[i][j+1].second]){
                printf("neispravna bojenje");
                return 0;
            }
            cused[adjlist[i][j+1].second] = true;
            if(cused[gcoloroflink(adjlist[i][j].first, adjlist[i][j+1].first)]){
                printf("neispravna bojenje");
                return 0;
            }
        }
    }
    printf("tocno");
}
/*
1 7
1111111
6 3 2
3 5 2
7 2 2
7 3 2
*/

Compilation message

checker.cpp: In function 'int main()':
checker.cpp:95:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j+1 < adjlist[i].size(); j++){
                        ~~~~^~~~~~~~~~~~~~~~~~~
checker.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
checker.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
checker.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%c", &c);
     ~~~~~^~~~~~~~~~
checker.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%c",&c);
         ~~~~~^~~~~~~~~
checker.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &f, &t, &col);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 245 ms 18584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 253 ms 18544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -