Submission #1135327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135327		duckindog	Joker (BOI20_joker)	C++17	25 / 100	955 ms	24588 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

struct LCT { 
  struct Node { 
    int l, r, p;
    bool flip;
    int valueMin, mi;
    int valueSum, sum;
    Node() : l(0), r(0), p(0), flip(false), valueMin(0), mi(0), 
              valueSum(0), sum(0) {}
  };

  vector<Node> a;
  LCT(int size) : a(size + 1) {}

  bool side(int u) const { 
    return a[a[u].p].r == u;
  }
  bool isRoot(int u) const { 
    return !a[u].p || (a[a[u].p].l != u && a[a[u].p].r != u);
  }
  void push(int u) { 
    if (a[u].flip) { 
      a[u].flip = false;
      swap(a[u].l, a[u].r);
      if (a[u].l) a[a[u].l].flip ^= 1;
      if (a[u].r) a[a[u].r].flip ^= 1;
    }
  }
  void pull(int u) { 
    a[u].sum = a[u].valueSum + a[a[u].l].sum + a[a[u].r].sum;

    int lt = a[a[u].l].mi, rt = a[a[u].r].mi;
    a[u].mi = u;
    if (a[a[u].mi].valueMin > a[lt].valueMin) a[u].mi = lt;
    if (a[a[u].mi].valueMin > a[rt].valueMin) a[u].mi = rt;
  }
  void attach(int u, int dir, int child) { 
    if (child) a[child].p = u;
    (dir ? a[u].r : a[u].l) = child;
    pull(u);
  }

  // SPLAY TREE OPERATOR
  void rotate(int u) {
    const int p = a[u].p, parP = a[p].p;
    push(p); push(u);
    
    if (!isRoot(p)) attach(parP, side(p), u);
    a[u].p = parP;
    
    const int dir = (a[p].r == u);
    attach(p, dir, dir ? a[u].l : a[u].r);
    attach(u, !dir, p);

    pull(parP);
  }
  void splay(int u) { 
    for (; !isRoot(u); rotate(u)) { 
      if (!isRoot(a[u].p))
        rotate(side(a[u].p) == side(u) ? a[u].p : u);
    }
    push(u);
  }
  // END TAG

  // BASE OPERATOR
  int access(int u) { 
    int last = 0;
    for (int p = u; p; p = a[p].p) {
      splay(p);
      a[p].r = last;
      pull(last = p);
    }
    splay(u);
    return last;
  }
  void makeRoot(int u) {
    access(u);
    if (a[u].l)
      a[a[u].l].flip = true, a[u].l = 0;
    pull(u);
  }
  // END TAG

  // QUERY OPERATOR
  int lca(int u, int v) { 
    if (u == v) return u;
    access(u);
    int ret = access(v);
    return a[u].p ? ret : 0;
  }
  bool isConnected(int u, int v) { 
    return lca(u, v); }

  int queryMin(int u, int v) { 
    makeRoot(u); 
    access(v);
    return a[v].mi;
  }
  int querySum(int u, int v) { 
    makeRoot(u); 
    access(v);
    return a[v].sum;
  }
  // END TAG

  // MODIFICATION
  void link(int u, int v) { 
    makeRoot(v);
    a[v].p = u;
  }
  void cut(int u) { 
    access(u);
    a[a[u].l].p = 0, a[u].l = 0;
    pull(u);
  }
  void cut(int u, int v) { 
    makeRoot(u);
    access(v);
    cut(v);
  }
  // END TAG
};

int32_t main() { 
  cin.tie()->sync_with_stdio(0);

  int n, m, q; cin >> n >> m >> q;
  
  vector<pair<int, int>> edge(m + 1);
  for (int i = 1; i <= m; ++i) cin >> edge[i].first >> edge[i].second;
  for (int i = 1; i <= m; ++i) 
    edge[i].first += 2 * m, edge[i].second += 2 * m;
  edge.insert(edge.end(), edge.begin() + 1, edge.end());

  LCT T(n + 2 * m);
  for (int i = 1; i <= 2 * m; ++i) 
    T.a[i].valueSum = 1, T.a[i].valueMin = i;
  T.a[0].valueMin = 1'000'000;
  for (int i = 2 * m + 1; i <= 2 * m + n; ++i)
    T.a[i].valueMin = 1'000'000;

  auto chk = [&](int idx) { 
    const auto& [u, v] = edge[idx];
    if (!T.isConnected(u, v)) return true;
    return T.querySum(u, v) % 2 != 0;
  };
  
  vector<bool> mk(2 * m + 1);
  auto cut = [&](int idx) { 
    assert(idx <= 2 * m);
    const auto& [u, v] = edge[idx];
    
    mk[idx] = false;
    T.cut(u, idx);
    T.cut(idx, v);
  };
  auto link = [&](int idx) { 
    const auto& [u, v] = edge[idx];
    if (T.isConnected(u, v)) cut(T.queryMin(u, v));
    
    mk[idx] = true;
    T.link(u, idx);
    T.link(idx, v);
  };

  vector<int> rightMost(2 * m + 1);
  for (int l = 1, r = 1; l <= 2 * m; ++l) { 
    while (r <= 2 * m && chk(r)) link(r++);
    rightMost[l] = r - 1;
    if (mk[l]) cut(l);
  }

  while (q--) { 
    int l, r; cin >> l >> r;
    cout << (rightMost[r + 1] < m + l ? "YES" : "NO") << "\n";
  }
}

• Subtask 1: 0 / 8
• Subtask 2: 25 / 25
• Subtask 3: 0 / 10
• Subtask 4: 0 / 22
• Subtask 5: 0 / 29
• Subtask 6: 0 / 6