제출 #203693

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
203693		fedoseevtimofey	Cats or Dogs (JOI18_catdog)	C++14	0 / 100	9 ms	8952 KiB

catdog

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <random>
#include <complex>
#include <iomanip>
#include <cassert>
#include <functional>
          
using namespace std;
        
typedef long long ll;

const int N = 1e5 + 7;
const int Inf = 1e9;

int n;

vector <int> g[N];
int par[N];


struct Node {
  int dp[2][2];
  Node() {
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        dp[i][j] = 0;
      }
    }
  }
  Node operator +(const Node &other) const {
    Node res;
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        res.dp[i][j] = Inf;
      }
    }
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        for (int k = 0; k < 2; ++k) {
          for (int t = 0; t < 2; ++t) {
            res.dp[i][t] = min(res.dp[i][t], dp[i][j] + other.dp[k][t] + (j != k));
          }
        }
      }
    }
    return res;
  } 
};

int sz[N];

void dfs(int u, int p) {
  par[u] = p;
  if (p != -1) {
    g[u].erase(find(g[u].begin(), g[u].end(), p));
  }
  sz[u] = 1;
  for (auto v : g[u]) {
    dfs(v, u);
  }
  sort(g[u].begin(), g[u].end(), [&] (int a, int b) {
    return sz[a] > sz[b];
  });
} 

vector <int> e;
int in[N], st[N], en[N];
int dp[N][2];

int hld(int u, int beg) {
  e.push_back(u);
  in[u] = (int)e.size() - 1;
  st[u] = beg;
  if (!g[u].empty()) {
    en[u] = hld(g[u][0], beg);
    for (int i = 1; i < (int)g[u].size(); ++i) {
      hld(g[u][i], g[u][i]);
    }
  } else {
    en[u] = u;
  }
  return en[u];
}

Node t[4 * N];

void build(int l, int r, int v) {
  if (l == r) {
    t[v].dp[0][0] = 0;
    t[v].dp[1][1] = 0;
    t[v].dp[0][1] = Inf;
    t[v].dp[1][0] = Inf;
  } else {
    int m = (l + r) >> 1;
    build(l, m, 2 * v + 1);
    build(m + 1, r, 2 * v + 2);
    t[v] = t[2 * v + 1] + t[2 * v + 2];
  }
}

void initialize(int _n, vector <int> a, vector <int> b) {
  n = _n;
  for (int i = 0; i + 1 < n; ++i) {
    --a[i], --b[i];
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }
  dfs(0, -1);
  hld(0, 0);
  build(0, n - 1, 0);
}

void modify(int id, pair <int, int> val, int l, int r, int v) {
  if (l == r) {
    t[v].dp[0][0] = val.first;
    t[v].dp[1][1] = val.second;
    t[v].dp[0][1] = Inf;
    t[v].dp[1][0] = Inf;
  } else {
    int m = (l + r) >> 1;
    if (id <= m) modify(id, val, l, m, 2 * v + 1);
    else modify(id, val, m + 1, r, 2 * v + 2);
    t[v] = t[2 * v + 1] + t[2 * v + 2];
  }
}

Node get(int ql, int qr, int l, int r, int v) {
  if (qr < l || r < ql) return Node();
  if (ql <= l && r <= qr) return t[v];
  int m = (l + r) >> 1;
  return get(ql, qr, l, m, 2 * v + 1) + get(ql, qr, m + 1, r, 2 * v + 2);
}
  
void update(int v) {
  //cout << "Update " << v + 1 << endl;
  while (v != -1) {
    Node bef = get(in[st[v]], in[en[v]], 0, n - 1, 0);
    modify(in[v], make_pair(dp[v][0], dp[v][1]), 0, n - 1, 0); 
    //cout << "Now in " << v + 1 << ' ' << dp[v][0] << ' ' << dp[v][1] << endl;
    Node aft = get(in[st[v]], in[en[v]], 0, n - 1, 0); 
    int u = par[st[v]];
    dp[u][0] -= min(min(bef.dp[0][0], bef.dp[1][0]), min(bef.dp[0][1], bef.dp[1][1]) + 1);
    dp[u][0] += min(min(aft.dp[0][0], aft.dp[1][0]), min(aft.dp[0][1], aft.dp[1][1]) + 1);
    dp[u][1] -= min(min(bef.dp[0][1], bef.dp[1][1]), min(bef.dp[0][0], bef.dp[1][0]) + 1);
    dp[u][1] += min(min(aft.dp[0][1], aft.dp[1][1]), min(aft.dp[0][0], aft.dp[1][0]) + 1);
    v = u;
  } 
}

int have[N];

int get() {
  int ret = Inf;
  Node res = get(in[st[0]], in[en[0]], 0, n - 1, 0);
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      ret = min(ret, res.dp[i][j]);
    }
  }
  return ret;
}

int cat(int v) {
  --v;
  dp[v][1] += Inf;
  have[v] = 0;
  update(v);
  return get();
}

int dog(int v) {
  --v;
  dp[v][0] += Inf;
  have[v] = 1;
  update(v);
  return get();
}

int neighbor(int v) {
  --v;
  if (have[v] == 0) dp[v][1] -= Inf;
  else if (have[v] == 1) dp[v][0] -= Inf;
  update(v);
  return get();
}
  
#ifdef LOCAL
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n;
  cin >> n;
  vector <int> a(n - 1), b(n - 1);
  for (int i = 0; i + 1 < n; ++i) {
    cin >> a[i] >> b[i];
  }
  initialize(n, a, b);  
  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int t, v;
    cin >> t >> v;
    if (t == 1) {
      cout << cat(v) << '\n';
    } else if (t == 2) {
      cout << dog(v) << '\n';
    } else {
      cout << neighbor(v) << '\n';
    }
  }
}
#endif

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