QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#791311	#8704. 排队	0x3b800001	100 ✓	427ms	42976kb	C++14	3.7kb	2024-11-28 18:00:48	2024-11-28 18:00:48

Judging History

你现在查看的是最新测评结果

[2024-11-28 18:00:48]
评测

测评结果：100
用时：427ms
内存：42976kb

查看

[2024-11-28 18:00:48]
提交

answer

#include <iostream>
#include <set>
#include <random>
#include <cassert>

namespace FHQ {
  std::mt19937 rng(0x3b800001);
  struct Node {
    int sz;
    unsigned rnd;
    int fa, ls, rs;
  } tr[600007];
  int nodecnt;
  int pushup(int p) {
    tr[p].sz = 1;
    if (tr[p].ls != 0) {
      tr[tr[p].ls].fa = p;
      tr[p].sz += tr[tr[p].ls].sz;
    }
    if (tr[p].rs != 0) {
      tr[tr[p].rs].fa = p;
      tr[p].sz += tr[tr[p].rs].sz;
    }
    tr[p].fa = 0;
    return p;
  }
  std::pair<int, int> split_by_sz(int p, int sz) {
    if (p == 0) {
      return {0, 0};
    }
    if (sz <= tr[tr[p].ls].sz) {
      auto [l, r] = split_by_sz(tr[p].ls, sz);
      tr[p].ls = r;
      return {l, pushup(p)};
    }
    auto [l, r] = split_by_sz(tr[p].rs, sz - tr[tr[p].ls].sz - 1);
    tr[p].rs = l;
    return {pushup(p), r};
  }
  int merge(int u, int v) {
    if (u == 0 || v == 0) {
      return u + v;
    }
    if (tr[u].rnd < tr[v].rnd) {
      v = merge(tr[u].rs, v);
      tr[u].rs = v;
      return pushup(u);
    }
    u = merge(u, tr[v].ls);
    tr[v].ls = u;
    return pushup(v);
  }
  int get_rank(int p) {
    int ans = tr[tr[p].ls].sz + 1;
    while (tr[p].fa != 0) {
      if (tr[tr[p].fa].rs == p) {
        ans += tr[tr[tr[p].fa].ls].sz + 1;
      }
      p = tr[p].fa;
    }
    return ans;
  }
  int get_anc(int p) {
    while (tr[p].fa != 0) {
      p = tr[p].fa;
    }
    return p;
  }
  int get_right(int p) {
    while (tr[p].rs != 0) {
      p = tr[p].rs;
    }
    return p;
  }
  int root;
  void insert(int u, int sz) {
    tr[u].rnd = rng();
    tr[u].sz = 1;
    auto [l, r] = split_by_sz(root, sz);
    root = merge(merge(l, u), r);
  }
};

int m, n;
int t[300007], fa[300007], tid[300007];
std::set<int> sons[300007];

namespace LCC {
  void insert(int i) { FHQ::tr[i + m + 2].rnd = FHQ::rng(), FHQ::tr[i + m + 2].sz = 1; }
  void link(int u, int v) { FHQ::merge(FHQ::get_anc(u + m + 2), FHQ::get_anc(v + m + 2)); }
  void cut(int u) { FHQ::split_by_sz(FHQ::get_anc(u + m + 2), FHQ::get_rank(u + m + 2)); }
  int get_anc(int u) { return FHQ::get_right(FHQ::get_anc(u + m + 2)) - m - 2; }
};

int main() {
	std::cin.tie(nullptr)->sync_with_stdio(false);
  std::cin >> m >> m;
  FHQ::insert(1, 0), LCC::insert(0);
  for (int i = 1; i <= m; ++i) {
    int op;
    std::cin >> op;
    if (op == 1) {
      ++n;
      t[n] = i, std::cin >> fa[n], tid[i] = n;
      FHQ::insert(n + 1, FHQ::get_rank(fa[n] + 1));
      LCC::insert(n);
      if (!sons[fa[n]].empty()) {
        LCC::cut(fa[n]);
      }
      sons[fa[n]].insert(i);
      LCC::link(fa[n], tid[*sons[fa[n]].begin()]);
    } else if (op == 2) {
      int j;
      std::cin >> j;

      int dfnl = FHQ::get_rank(j + 1), dfnr = FHQ::get_rank(LCC::get_anc(j) + 1);
      auto [l, mr] = FHQ::split_by_sz(FHQ::root, dfnl - 1);
      auto [mid, r] = FHQ::split_by_sz(mr, dfnr - dfnl + 1);
      FHQ::root = FHQ::merge(l, r);

      LCC::cut(fa[j]);
      sons[fa[j]].erase(t[j]);
      if (!sons[fa[j]].empty()) {
        LCC::link(fa[j], tid[*sons[fa[j]].begin()]);
      }
      
      std::cin >> fa[j];

      int aft = fa[j];
      auto it = sons[fa[j]].lower_bound(t[j]);
      if (it != sons[fa[j]].end()) {
        aft = LCC::get_anc(tid[*it]);
      }
      aft = FHQ::get_rank(aft + 1);
      auto [L, R] = FHQ::split_by_sz(FHQ::root, aft);
      FHQ::root = FHQ::merge(FHQ::merge(L, mid), R);

      if (!sons[fa[j]].empty()) {
        LCC::cut(fa[j]);
      }
      sons[fa[j]].insert(t[j]);
      LCC::link(fa[j], tid[*sons[fa[j]].begin()]);
      
    } else {
      int x;
      std::cin >> x;
      std::cout << FHQ::get_rank(x + 1) - 1 << '\n';
    }
  }
  return 0;
}

源文件, 语言: C++14

详细

Subtask #1:

score: 4

Accepted

Test #1:

score: 4

Accepted

time: 0ms

memory: 22448kb

input:

output:

result:

ok 4 lines

Test #2:

score: 4

Accepted

time: 0ms

memory: 23164kb

input:

output:

result:

ok 153 lines

Test #3:

score: 4

Accepted

time: 0ms

memory: 22556kb

input:

output:

result:

ok 159 lines

Test #4:

score: 4

Accepted

time: 0ms

memory: 22160kb

input:

output:

result:

ok 145 lines

Subtask #2:

score: 19

Accepted

Test #5:

score: 19

Accepted

time: 126ms

memory: 33004kb

input:

output:

result:

ok 179182 lines

Test #6:

score: 19

Accepted

time: 150ms

memory: 40584kb

input:

output:

result:

ok 98880 lines

Test #7:

score: 19

Accepted

time: 165ms

memory: 35228kb

input:

output:

result:

ok 148504 lines

Test #8:

score: 19

Accepted

time: 125ms

memory: 34120kb

input:

output:

result:

ok 167157 lines

Test #9:

score: 19

Accepted

time: 148ms

memory: 35328kb

input:

output:

result:

ok 145645 lines

Test #10:

score: 19

Accepted

time: 132ms

memory: 37280kb

input:

output:

result:

ok 148730 lines

Test #11:

score: 19

Accepted

time: 97ms

memory: 30592kb

input:

output:

result:

ok 234925 lines

Test #12:

score: 19

Accepted

time: 157ms

memory: 38520kb

input:

output:

result:

ok 126807 lines

Test #13:

score: 19

Accepted

time: 145ms

memory: 36472kb

input:

output:

result:

ok 126007 lines

Test #14:

score: 19

Accepted

time: 155ms

memory: 40252kb

input:

output:

result:

ok 97400 lines

Test #15:

score: 19

Accepted

time: 156ms

memory: 40828kb

input:

output:

result:

ok 117628 lines

Test #16:

score: 19

Accepted

time: 118ms

memory: 31744kb

input:

output:

result:

ok 194540 lines

Test #17:

score: 19

Accepted

time: 205ms

memory: 41972kb

input:

output:

result:

ok 74993 lines

Test #18:

score: 19

Accepted

time: 149ms

memory: 41656kb

input:

output:

result:

ok 98914 lines

Test #19:

score: 19

Accepted

time: 137ms

memory: 34812kb

input:

output:

result:

ok 166650 lines

Subtask #3:

score: 21

Accepted

Test #20:

score: 21

Accepted

time: 108ms

memory: 28392kb

input:

output:

result:

ok 222965 lines

Test #21:

score: 21

Accepted

time: 105ms

memory: 33136kb

input:

output:

result:

ok 197988 lines

Test #22:

score: 21

Accepted

time: 218ms

memory: 42976kb

input:

output:

result:

ok 58684 lines

Test #23:

score: 21

Accepted

time: 150ms

memory: 38796kb

input:

output:

result:

ok 117694 lines

Test #24:

score: 21

Accepted

time: 131ms

memory: 35684kb

input:

output:

result:

ok 147378 lines

Test #25:

score: 21

Accepted

time: 138ms

memory: 36972kb

input:

output:

result:

ok 144784 lines

Test #26:

score: 21

Accepted

time: 148ms

memory: 40288kb

input:

output:

result:

ok 116141 lines

Test #27:

score: 21

Accepted

time: 144ms

memory: 37048kb

input:

output:

result:

ok 147525 lines

Test #28:

score: 21

Accepted

time: 134ms

memory: 38204kb

input:

output:

result:

ok 148070 lines

Test #29:

score: 21

Accepted

time: 153ms

memory: 41972kb

input:

output:

result:

ok 97860 lines

Test #30:

score: 21

Accepted

time: 139ms

memory: 40576kb

input:

output:

result:

ok 96730 lines

Test #31:

score: 21

Accepted

time: 159ms

memory: 41016kb

input:

output:

result:

ok 98247 lines

Test #32:

score: 21

Accepted

time: 112ms

memory: 33648kb

input:

output:

result:

ok 167688 lines

Test #33:

score: 21

Accepted

time: 171ms

memory: 39496kb

input:

output:

result:

ok 117234 lines

Test #34:

score: 21

Accepted

time: 146ms

memory: 38412kb

input:

output:

result:

ok 149568 lines

Subtask #4:

score: 23

Accepted

Test #35:

score: 23

Accepted

time: 366ms

memory: 32052kb

input:

output:

result:

ok 99743 lines

Test #36:

score: 23

Accepted

time: 362ms

memory: 32968kb

input:

output:

result:

ok 99750 lines

Test #37:

score: 23

Accepted

time: 361ms

memory: 33844kb

input:

output:

result:

ok 99683 lines

Subtask #5:

score: 33

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Test #38:

score: 33

Accepted

time: 318ms

memory: 33140kb

input:

output:

result:

ok 98966 lines

Test #39:

score: 33

Accepted

time: 427ms

memory: 26592kb

input:

output:

result:

ok 48520 lines

Test #40:

score: 33

Accepted

time: 319ms

memory: 25928kb

input:

output:

result:

ok 108743 lines

Test #41:

score: 33

Accepted

time: 329ms

memory: 31080kb

input:

output:

result:

ok 87130 lines

Test #42:

score: 33

Accepted

time: 335ms

memory: 32028kb

input:

output:

result:

ok 74076 lines

Test #43:

score: 33

Accepted

time: 328ms

memory: 32392kb

input:

output:

result:

ok 88582 lines

Test #44:

score: 33

Accepted

time: 192ms

memory: 28636kb

input:

output:

result:

ok 198778 lines

Test #45:

score: 33

Accepted

time: 247ms

memory: 31388kb

input:

output:

result:

ok 145139 lines

Test #46:

score: 33

Accepted

time: 259ms

memory: 25784kb

input:

output:

result:

ok 147109 lines

Test #47:

score: 33

Accepted

time: 273ms

memory: 29216kb

input:

output:

result:

ok 116820 lines

Test #48:

score: 33

Accepted

time: 251ms

memory: 30236kb

input:

output:

result:

ok 150091 lines

Test #49:

score: 33

Accepted

time: 369ms

memory: 33944kb

input:

output:

result:

ok 64514 lines

Test #50:

score: 33

Accepted

time: 220ms

memory: 35052kb

input:

output:

result:

ok 109540 lines

Test #51:

score: 33

Accepted

time: 183ms

memory: 30296kb

input:

output:

result:

ok 197757 lines

Test #52:

score: 33

Accepted

time: 252ms

memory: 33660kb

input:

output:

result:

ok 119220 lines