제출 #1205224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205224		akamizane	Cats or Dogs (JOI18_catdog)	C++20	0 / 100	3 ms	5696 KiB

catdog

#include<bits/stdc++.h>

using namespace std;

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;
   for (auto v : ad[u]){
      if (v == p) continue;
      par[v] = u;
      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));
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 30
• Subtask 3: 0 / 62