oj.uz

Submission #404932

# Submission time Handle Problem Language Result Execution time Memory
404932 2021-05-15T10:21:10 Z Andyvanh1 Checker (COCI19_checker) C++14
23 / 110
 325 ms 22800 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <fstream>
#include <math.h>

using namespace std;

#define vt vector
#define INF 0x3f3f3f3f
#define pb push_back
#define FORR1(n) for(int i = 0; i < n; i++)
#define FORR2(i,n) for(int i = 0; i < n; i++)
#define all(u) u.begin(),u.end()

typedef long long ll;
typedef vt<int> vi;
typedef pair<int,int> pii;

struct CTD{
    int size;
    vi par;
    vt<set<int>> tree;
    vi sub;
    void init(vt<set<int>> &adj){
        size = adj.size();
        par.resize(size);
        tree=adj;
        sub.resize(size);
        par[0] = -1;
        build(0,-1);
    }
    void build(int u, int p) {
        int n = dfs(u, p); // find the size of each subtree
        int centroid = find_centroid(u, p, n); // find the centroid
        par[centroid] = p;

        // for each tree resulting from the removal of the centroid
        set<int> ref = tree[centroid];
        for (auto v : ref) {
            tree[centroid].erase(v); // remove the edge to disconnect
            tree[v].erase(centroid); // the component from the tree
            build(v, centroid);
        }
    }



    int dfs(int u, int p) {
        sub[u] = 1;

        for (auto v : tree[u])
            if (v != p) sub[u] += dfs(v, u);

        return sub[u];
    }

    int find_centroid(int node, int p, int n){
        for(auto& e: tree[node]){
            if(e!=p&&sub[e]>n/2){
                return find_centroid(e,node,n);
            }
        }
        return node;
    }


};

struct fwtree{
    int size;
    vi arr;
    void init(int n){
        size = n;
        arr.resize(n+2);
        for(int i = 0; i < n+2; i++){
            arr[i] = 0;
        }
    }

    void update(int i, int x){
        for(; i <= size; i+=i&-i){
            arr[i]+=x;
        }
    }

    int get(int i){
        int ans = 0;
        for(; i > 0; i-=i&-i){
            ans+=arr[i];
        }
        return ans;
    }

    int get(int l, int r){
        return get(r)-get(l-1);
    }

};

struct point{
    long double x, y;

};

bool operator<(point p1, point p2){
    return p2.x>p1.x||(p2.x==p1.x&&p2.y>p1.y);
}
vt<pair<int,int>> adjlist[200005];
void solve(){
   int n;
   cin>>n;
   cin>>n;
   string s;
   cin>>s;
   vi colors(n);
   for(int i = 0; i < n; i++){
       colors[i] = s[i]-'0';
   }
   for(int i = 0; i < n; i++){
       int j1, j2;
       if(i!=n-1){
           j1 = i+1;
       }else{
           j1 = 0;
       }
       if(i!=0){
           j2 = i-1;
       }else{
           j2 = n-1;
       }
       adjlist[i].pb({j2,colors[j2]});
       adjlist[i].pb({j1,colors[i]});

   }
   for(int i = 0; i < n-3; i++){
       int u,v,c;
       cin>>u>>v>>c;u--;v--;
       adjlist[u].pb({v,c});
       adjlist[v].pb({u,c});
   }
   bool bol = true;
   for(int i = 0; i < n; i++){
       vt<pii> e = adjlist[i];
       sort(all(e));
       if(e.size()==2){
           if(e[0].second==e[1].second){
               bol = false;

               continue;
           }
       }


       for(int j = 0; j < e.size()-1; j++){
           if(e[j].first==(i==0?n-1:i-1)&&e[j+1].first==(i==n-1?0:i+1)){
               continue;
           }
           if(e[j+1].second==e[j].second){
               bol = false;

           }
       }
       if(e[0].second==e[e.size()-1].second){
           if(!(e[0].first==1&&e[e.size()-1].first==n-1||e[0].first==0&&e[e.size()-1].first==n-2))
           bol = false;

       }
   }



   cout<<(bol?"tocno":"neispravno bojenje");

}

int main() {
    solve();
    return 0;
}

Compilation message

checker.cpp: In function 'void solve()':
checker.cpp:157:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |        for(int j = 0; j < e.size()-1; j++){
      |                       ~~^~~~~~~~~~~~
checker.cpp:167:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  167 |            if(!(e[0].first==1&&e[e.size()-1].first==n-1||e[0].first==0&&e[e.size()-1].first==n-2))

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Incorrect 4 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Incorrect 4 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 22208 KB Output is correct
2 Correct 310 ms 22096 KB Output is correct
3 Incorrect 322 ms 22284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 22172 KB Output is correct
2 Correct 319 ms 22176 KB Output is correct
3 Correct 310 ms 22092 KB Output is correct
4 Correct 314 ms 22160 KB Output is correct
5 Correct 325 ms 22200 KB Output is correct
6 Correct 316 ms 22620 KB Output is correct
7 Correct 314 ms 22640 KB Output is correct
8 Correct 321 ms 22800 KB Output is correct
9 Correct 317 ms 22784 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Incorrect 4 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -