Submission #441119

#	Time	Username	Problem	Language	Result	Execution time	Memory
441119		peijar	Synchronization (JOI13_synchronization)	C++17	100 / 100	235 ms	11860 KiB

synchronization

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct SplayTree {
  struct Node {
    int ch[2] = {0, 0}, p = 0;
    int self = 0, path = 0;
    int sub = 0, vir = 0;
    bool flip = 0;
  };
  vector<Node> T;

  SplayTree(int n) : T(n + 1) {}

  void push(int x) {
    if (!x || !T[x].flip)
      return;
    int l = T[x].ch[0], r = T[x].ch[1];

    T[l].flip ^= 1, T[r].flip ^= 1;
    swap(T[x].ch[0], T[x].ch[1]);
    T[x].flip = 0;
  }

  void pull(int x) {
    int l = T[x].ch[0], r = T[x].ch[1];
    push(l);
    push(r);
    T[x].path = T[l].path + T[x].self + T[r].path;
    T[x].sub = T[x].vir + T[l].sub + T[r].sub + T[x].self;
  }

  void set(int x, int d, int y) {
    T[x].ch[d] = y, T[y].p = x;
    pull(x);
  }

  void splay(int x) {
    auto dir = [&](int x) {
      int p = T[x].p;
      if (!p)
        return -1;
      return T[p].ch[0] == x ? 0 : T[p].ch[1] == x ? 1 : -1;
    };
    auto rotate = [&](int x) {
      int y = T[x].p, z = T[y].p, dx = dir(x), dy = dir(y);
      set(y, dx, T[x].ch[!dx]);
      set(x, !dx, y);
      if (~dy)
        set(z, dy, x);
      T[x].p = z;
    };
    for (push(x); ~dir(x);) {
      int y = T[x].p, z = T[y].p;
      push(z);
      push(y);
      push(x);
      int dx = dir(x), dy = dir(y);
      if (~dy)
        rotate(dx != dy ? x : y);
      rotate(x);
    }
  }
};

struct LinkCut : SplayTree {
  LinkCut(int n) : SplayTree(n) {}

  int access(int x) {
    int u = x, v = 0;
    for (; u; v = u, u = T[u].p) {
      splay(u);
      int &ov = T[u].ch[1];
      T[u].vir += T[ov].sub;
      T[u].vir -= T[v].sub;
      ov = v;
      pull(u);
    }
    splay(x);
    return v;
  }

  void reroot(int x) {
    access(x);
    T[x].flip ^= 1;
    push(x);
  }

  void link(int u, int v) {
    ++u, ++v;
    reroot(u);
    access(v);
    T[v].vir += T[u].sub;
    T[u].p = v;
    pull(v);
  }

  void cut(int u, int v) {
    ++u, ++v;
    reroot(u);
    access(v);
    T[v].ch[0] = T[u].p = 0;
    pull(v);
  }

  int lca(int u, int v) {
    ++u, ++v;
    if (u == v)
      return u;
    access(u);
    int ret = access(v);
    return T[u].p ? ret : 0;
  }

  int subTree(int u,
              int v) // Calculates subtree aggregate for u when rooted at v
  {
    ++u, ++v;
    reroot(v);
    access(u);
    return T[u].vir + T[u].self;
  }

  int path(int u, int v) // puts v at root, and path to u is in left child.
  {
    ++u, ++v;
    reroot(u);
    access(v);
    return T[v].path;
  }

  void update(int u, int v) {
    ++u;
    access(u);
    T[u].self = v;
    pull(u);
  }
};

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommets, nbUpdates, nbRequetes;
  cin >> nbSommets >> nbUpdates >> nbRequetes;
  vector<pair<int, int>> aretes(nbSommets - 1);
  for (auto &[u, v] : aretes) {
    cin >> u >> v;
    --u, --v;
  }

  LinkCut lct(nbSommets);
  for (int i = 0; i < nbSommets; ++i) {
    lct.update(i, 1);
  }
  vector<bool> state(nbSommets - 1);
  vector<int> lstVal(nbSommets - 1);

  for (int i = 0; i < nbUpdates; ++i) {
    /*cout << "AFTER " << i << " UPDATES : " << endl;
    for (int j = 0; j < nbSommets; ++j)
      cout << lct.subTree(j, j) << ' ';
    cout << endl;*/
    int x;
    cin >> x;
    --x;
    auto [u, v] = aretes[x];
    if (!state[x]) {
      lct.link(u, v);
      lct.update(u, lct.T[u + 1].self - lstVal[x]);
    } else {
      int cur = lct.subTree(u, u);
      lstVal[x] = cur;
      lct.cut(u, v);
      int valU = lct.subTree(u, u);
      int valV = lct.subTree(v, v);
      lct.update(u, lct.T[u + 1].self + valV);
      lct.update(v, lct.T[v + 1].self + valU);
    }
    state[x] = !state[x];
  }
  for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) {
    int u;
    cin >> u;
    --u;
    cout << lct.subTree(u, u) << '\n';
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40