Submission #1205215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205215		akamizane	Cats or Dogs (JOI18_catdog)	C++20	Compilation error	0 ms	0 KiB

catdog

#include<bits/stdc++.h>
#include "catdog.h"

using namespace std;

#define int long long

const int maxn = 1e5 + 5;
const int inf = 1e9;

struct Node {
   int dp[2][2];
   Node (int cat = 0, int dog = 0){
      dp[0][0] = cat;
      dp[1][1] = dog;
      dp[0][1] = dp[1][0] = inf;
   } 
   friend Node operator + (Node left, Node right){
      Node ans = Node(inf, inf);
      for (int l = 0; l < 2; l++){
         for (int r = 0; r < 2; r++){
            for (int a = 0; a < 2; a++){
               for (int b = 0; b < 2; b++){
                  ans.dp[l][r] = min(ans.dp[l][r], left.dp[l][a] + right.dp[b][r] + (a ^ b));
               }
            }
         }
      }
      return ans;
   }
};

struct Segtree {
   int n;
   vector<Node> t;
   Segtree(){}
   Segtree(int _n){
      n = _n;
      t.resize((n << 2) + 1);
   } 
   void update(int id, int l, int r, int pos, int cat, int dog){
      if (l == r){
         t[id].dp[0][0] += cat;
         t[id].dp[1][1] += dog;
         return;
      }
      else{
         int m = (l + r) >> 1;
         if (pos <= m) update(id << 1, l, m, pos, cat, dog);
         else update(id << 1 | 1, m + 1, r, pos, cat, dog);
         t[id] = t[id << 1] + t[id << 1 | 1]; 
      }
   }
   void upd(int pos, int cat, int dog){
      update(1, 1, n, pos, cat, dog);
   }

   int cat(){
      return min(t[1].dp[0][1], t[1].dp[0][0]);
   }

   int dog(){
      return min(t[1].dp[1][0], t[1].dp[1][1]);
   }
};

int sz[maxn], head[maxn], inChain[maxn], par[maxn], id[maxn], type[maxn], cursz[maxn], tin[maxn], pre[2][maxn], timeDfs, Chain, n;
vector<int> ad[maxn];
Segtree st[maxn];

void dfs(int u, int p){
   sz[u] = 1;
   par[u] = p;
   for (auto v : ad[u]){
      if (v == p) continue;
      dfs(v, u);
      sz[u] += sz[v];
   }
}

void hld (int u, int p){
   id[u] = Chain;
   tin[u] = ++timeDfs;
   if (!head[Chain]) head[Chain] = u;
   if (cursz[Chain] = 0) cursz[Chain] = 1;
   inChain[u] = cursz[Chain]++;
   int nxt = 0;
   for (auto v : ad[u]){
      if (v == p) continue;
      if (sz[v] > sz[nxt]) nxt = v;
   }
   if (nxt) hld(nxt, u);
   for (auto v : ad[u]){
      if (v == p || v == nxt) continue;
      Chain++;
      hld(v, u);
   }  
}

int update(int u, int ncat, int ndog){
   st[id[u]].upd(inChain[u], ncat, ndog);
   while(u){
      int v = par[head[id[u]]];
      if (v){
         st[id[v]].upd(inChain[v], -pre[0][id[u]], -pre[1][id[u]]);
      }
      pre[0][id[u]] = min(st[id[u]].cat(), st[id[u]].dog() + 1);
      pre[0][id[u]] = min(st[id[u]].dog(), st[id[u]].cat() + 1);
      if (v){
         st[id[v]].upd(inChain[v], pre[0][id[u]], pre[1][id[u]]);
      }
      u = par[head[id[u]]];
   }
   return min(st[1].dog(), st[1].cat());
}

void initialize(int N, vector<int> A, vector<int> B){
   n = N;
   for(int i = 0; i < n - 1; i++){
      ad[A[i]].push_back(B[i]);
      ad[B[i]].push_back(A[i]);
   }
   dfs(1, -1);
   Chain = 1, timeDfs = 0;
   hld(1, -1);
   for(int i = 1; i <= Chain; i++) st[i] = Segtree(cursz[i]);
}

int cat (int u){
   type[u] = 1;
   return update(u, 0, maxn);
}

int dog(int u){
   type[u] = 2;
   return update(u, maxn, 0);
}

int neighbor(int u){
   int val = type[u];
   type[u] = 0;
   return (val == 1 ? update(u, 0, - n) : update(u, -n, 0));
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc17cofI.o: in function `main':
grader.cpp:(.text.startup+0x1dc): undefined reference to `initialize(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: grader.cpp:(.text.startup+0x219): undefined reference to `neighbor(int)'
/usr/bin/ld: grader.cpp:(.text.startup+0x258): undefined reference to `dog(int)'
/usr/bin/ld: grader.cpp:(.text.startup+0x261): undefined reference to `cat(int)'
collect2: error: ld returned 1 exit status