Submission #649968

#	Time	Username	Problem	Language	Result	Execution time	Memory
649968		enerelt14	Cats or Dogs (JOI18_catdog)	C++14	Compilation error	0 ms	0 KiB

catdog

#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
const int MX=1e5+5;
int n, sz[MX], par[MX], num[MX];
int hldpar[MX], pos[MX], st[MX];
vector<int>adj[MX];
void dfs(int u, int pre){
    sz[u]=1;
    par[u]=pre;
    for (int i=0;i<adj[u].size();i++){
        int v=adj[u][i];
        if (v==pre)continue;
        dfs(v, u);
        sz[u]+=sz[v];
    }
}
void hld(int u, int pre){
    num[u]++;
    pos[u]=num[pre];
    hldpar[u]=pre;
    for (int i=0;i<adj[u].size();i++){
        int v=adj[u][i];
        if (v==par[u])continue;
        if (sz[v]*2>=sz[u])hld(v, pre);
        else hld(v, v);
    }
}
 
struct mat {
    int a00, a01, a10, a11;
 
    friend mat operator * (const mat& A, const mat& B) {
        mat R;
        R.a00 = min(A.a00 + B.a00, A.a01 + B.a10);
        R.a01 = min(A.a00 + B.a01, A.a01 + B.a11);
        R.a10 = min(A.a10 + B.a00, A.a11 + B.a10);
        R.a11 = min(A.a10 + B.a01, A.a11 + B.a11);
        return R;
    }
};
 
struct segtree {
    int s;
    vector<mat> cost;
 
    segtree() {}
    
    segtree(int n) {
        for (s = 1; s < n; s *= 2) {}
        cost = vector<mat>(2*s);
        for (int i = 0; i < 2*s; i++) {
            cost[i].a01 = cost[i].a10 = 1;
        }
    }
 
    void update(int i, int& v0, int& v1) {
        i += s;
        cost[i].a00 += v0;
        cost[i].a01 += v0;
        cost[i].a10 += v1;
        cost[i].a11 += v1;
        for (i /= 2; i; i /= 2) {
            cost[i] = cost[2*i] * cost[2*i+1];
        }
    }
 
    void eval(int& a0, int& a1) {
        a0 = min(cost[1].a00, cost[1].a01);
        a1 = min(cost[1].a10, cost[1].a11);
    }
} seg[MAXN];
 
void initialize(int n, std::vector<int> a, std::vector<int> b) {
    N = n;
    for (int i = 0; i < N-1; i++) {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
    for (int i = 1; i <= N; i++) st[i] = 0;
    dfs(1, 0);
    hld(1, 1);
    for (int i = 1; i <= N; i++) {
        assert((pos[i] == 0) == (hldpar[i] == i));
        if (hldpar[i] == i) seg[i] = segtree(num[i]);
    }
}
 
void update(int cur, int v0, int v1) {
    while (cur) {
        int top = hldpar[cur];
        int cur0, cur1, nxt0, nxt1;
        seg[top].eval(cur0, cur1);
        seg[top].update(pos[cur], v0, v1);
        seg[top].eval(nxt0, nxt1);
        v0 = min(nxt0, nxt1+1) - min(cur0, cur1+1);
        v1 = min(nxt0+1, nxt1) - min(cur0+1, cur1);
        cur = par[top];
    }
}
 
int query();
 
int cat(int v) {
    st[v] = 1;
    update(v, 0, N);
    return query();
}
 
int dog(int v) {
    st[v] = 2;
    update(v, N, 0);
    return query();
}
 
int neighbor(int v) {
    if (st[v] == 1) update(v, 0, -N);
    else if (st[v] == 2) update(v, -N, 0);
    else assert(false);
    st[v] = 0;
    return query();
}
 
int query() {
    int a0, a1;
    seg[1].eval(a0, a1);
    return min(a0, a1);
}

Compilation message (stderr)

catdog.cpp: In function 'void dfs(int, int)':
catdog.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i=0;i<adj[u].size();i++){
      |                  ~^~~~~~~~~~~~~~
catdog.cpp: In function 'void hld(int, int)':
catdog.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i=0;i<adj[u].size();i++){
      |                  ~^~~~~~~~~~~~~~
catdog.cpp: At global scope:
catdog.cpp:72:7: error: 'MAXN' was not declared in this scope; did you mean 'MX'?
   72 | } seg[MAXN];
      |       ^~~~
      |       MX
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:75:5: error: 'N' was not declared in this scope
   75 |     N = n;
      |     ^
catdog.cpp:85:29: error: 'seg' was not declared in this scope
   85 |         if (hldpar[i] == i) seg[i] = segtree(num[i]);
      |                             ^~~
catdog.cpp: In function 'void update(int, int, int)':
catdog.cpp:93:9: error: 'seg' was not declared in this scope
   93 |         seg[top].eval(cur0, cur1);
      |         ^~~
catdog.cpp: In function 'int cat(int)':
catdog.cpp:106:18: error: 'N' was not declared in this scope
  106 |     update(v, 0, N);
      |                  ^
catdog.cpp: In function 'int dog(int)':
catdog.cpp:112:15: error: 'N' was not declared in this scope
  112 |     update(v, N, 0);
      |               ^
catdog.cpp: In function 'int neighbor(int)':
catdog.cpp:117:35: error: 'N' was not declared in this scope
  117 |     if (st[v] == 1) update(v, 0, -N);
      |                                   ^
catdog.cpp:118:37: error: 'N' was not declared in this scope
  118 |     else if (st[v] == 2) update(v, -N, 0);
      |                                     ^
catdog.cpp: In function 'int query()':
catdog.cpp:126:5: error: 'seg' was not declared in this scope
  126 |     seg[1].eval(a0, a1);
      |     ^~~