QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185574#4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》hos_lyric#10 1761ms363308kbC++1410.1kb2023-09-22 12:13:042024-07-04 02:45:53

Judging History

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

  • [2024-07-04 02:45:53]
  • 评测
  • 测评结果:10
  • 用时:1761ms
  • 内存:363308kb
  • [2023-09-22 12:13:04]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


struct Hld {
  int n, rt;
  // needs to be tree
  // vertex lists
  // modified in build(rt) (parent removed, heavy child first)
  vector<vector<int>> graph;
  vector<int> sz, par, dep;
  int zeit;
  vector<int> dis, fin, sid;
  // head vertex (minimum depth) in heavy path
  vector<int> head;

  Hld() : n(0), rt(-1), zeit(0) {}
  explicit Hld(int n_) : n(n_), rt(-1), graph(n), zeit(0) {}
  void ae(int u, int v) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  void dfsSz(int u) {
    sz[u] = 1;
    for (const int v : graph[u]) {
      auto it = std::find(graph[v].begin(), graph[v].end(), u);
      if (it != graph[v].end()) graph[v].erase(it);
      par[v] = u;
      dep[v] = dep[u] + 1;
      dfsSz(v);
      sz[u] += sz[v];
    }
  }
  void dfsHld(int u) {
    dis[u] = zeit++;
    const int deg = graph[u].size();
    if (deg > 0) {
      int vm = graph[u][0];
      int jm = 0;
      for (int j = 1; j < deg; ++j) {
        const int v = graph[u][j];
        if (sz[vm] < sz[v]) {
          vm = v;
          jm = j;
        }
      }
      swap(graph[u][0], graph[u][jm]);
      head[vm] = head[u];
      dfsHld(vm);
      for (int j = 1; j < deg; ++j) {
        const int v = graph[u][j];
        head[v] = v;
        dfsHld(v);
      }
    }
    fin[u] = zeit;
  }
  void build(int rt_) {
    assert(0 <= rt_); assert(rt_ < n);
    rt = rt_;
    sz.assign(n, 0);
    par.assign(n, -1);
    dep.assign(n, -1);
    dep[rt] = 0;
    dfsSz(rt);
    zeit = 0;
    dis.assign(n, -1);
    fin.assign(n, -1);
    head.assign(n, -1);
    head[rt] = rt;
    dfsHld(rt);
    assert(zeit == n);
    sid.assign(n, -1);
    for (int u = 0; u < n; ++u) sid[dis[u]] = u;
  }

  friend ostream &operator<<(ostream &os, const Hld &hld) {
    const int maxDep = *max_element(hld.dep.begin(), hld.dep.end());
    vector<string> ss(2 * maxDep + 1);
    int pos = 0, maxPos = 0;
    for (int j = 0; j < hld.n; ++j) {
      const int u = hld.sid[j];
      const int d = hld.dep[u];
      if (hld.head[u] == u) {
        if (j != 0) {
          pos = maxPos + 1;
          ss[2 * d - 1].resize(pos, '-');
          ss[2 * d - 1] += '+';
        }
      } else {
        ss[2 * d - 1].resize(pos, ' ');
        ss[2 * d - 1] += '|';
      }
      ss[2 * d].resize(pos, ' ');
      ss[2 * d] += std::to_string(u);
      if (maxPos < static_cast<int>(ss[2 * d].size())) {
        maxPos = ss[2 * d].size();
      }
    }
    for (int d = 0; d <= 2 * maxDep; ++d) os << ss[d] << '\n';
    return os;
  }

  bool contains(int u, int v) const {
    return (dis[u] <= dis[v] && dis[v] < fin[u]);
  }
  int lca(int u, int v) const {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    for (; head[u] != head[v]; ) (dis[u] > dis[v]) ? (u = par[head[u]]) : (v = par[head[v]]);
    return (dis[u] > dis[v]) ? v : u;
  }
  int jumpUp(int u, int d) const {
    assert(0 <= u); assert(u < n);
    assert(d >= 0);
    if (dep[u] < d) return -1;
    const int tar = dep[u] - d;
    for (u = head[u]; ; u = head[par[u]]) {
      if (dep[u] <= tar) return sid[dis[u] + (tar - dep[u])];
    }
  }
  int jump(int u, int v, int d) const {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    assert(d >= 0);
    const int l = lca(u, v);
    const int du = dep[u] - dep[l], dv = dep[v] - dep[l];
    if (d <= du) {
      return jumpUp(u, d);
    } else if (d <= du + dv) {
      return jumpUp(v, du + dv - d);
    } else {
      return -1;
    }
  }
  // [u, v) or [u, v]
  template <class F> void doPathUp(int u, int v, bool inclusive, F f) const {
    assert(contains(v, u));
    for (; head[u] != head[v]; u = par[head[u]]) f(dis[head[u]], dis[u] + 1);
    if (inclusive) {
      f(dis[v], dis[u] + 1);
    } else {
      if (v != u) f(dis[v] + 1, dis[u] + 1);
    }
  }
  // not path order, include lca(u, v) or not
  template <class F> void doPath(int u, int v, bool inclusive, F f) const {
    const int l = lca(u, v);
    doPathUp(u, l, false, f);
    doPathUp(v, l, inclusive, f);
  }

  // (vs, ps): compressed tree
  // vs: DFS order (sorted by dis)
  // vs[ps[x]]: the parent of vs[x]
  // ids[vs[x]] = x, not set for non-tree vertex
  vector<int> ids;
  pair<vector<int>, vector<int>> compress(vector<int> us) {
    // O(n) first time
    ids.resize(n, -1);
    std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
      return (dis[u] < dis[v]);
    });
    us.erase(std::unique(us.begin(), us.end()), us.end());
    int usLen = us.size();
    assert(usLen >= 1);
    for (int x = 1; x < usLen; ++x) us.push_back(lca(us[x - 1], us[x]));
    std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
      return (dis[u] < dis[v]);
    });
    us.erase(std::unique(us.begin(), us.end()), us.end());
    usLen = us.size();
    for (int x = 0; x < usLen; ++x) ids[us[x]] = x;
    vector<int> ps(usLen, -1);
    for (int x = 1; x < usLen; ++x) ps[x] = ids[lca(us[x - 1], us[x])];
    return make_pair(us, ps);
  }
};

////////////////////////////////////////////////////////////////////////////////


constexpr int E = 62;

int N;
vector<int> A, B;
vector<Int> C;
int Q;

Hld hld;

vector<Int> Csid;
int jss[E + 1][1'000'010];

void dfs(int e, int l, int r) {
  if (e == 0) return;
  if (l == r) return;
  int pos = l;
  for (int k = l; k < r; ++k) {
    const int j = jss[e][k];
    if (!(Csid[j] >> (e-1) & 1)) jss[e-1][pos++] = j;
  }
  const int mid = pos;
  for (int k = l; k < r; ++k) {
    const int j = jss[e][k];
    if (Csid[j] >> (e-1) & 1) jss[e-1][pos++] = j;
  }
  dfs(e-1, l, mid);
  dfs(e-1, mid, r);
}

vector<Int> below;

void build() {
  hld = Hld(N);
  for (int i = 0; i < N - 1; ++i) {
    hld.ae(A[i], B[i]);
  }
  hld.build(0);
// cerr<<hld<<endl;
  
  Csid.resize(N);
  for (int j = 0; j < N; ++j) {
    Csid[j] = C[hld.sid[j]];
  }
  for (int j = 0; j < N; ++j) {
    jss[E][j] = j;
  }
  dfs(E, 0, N);
// for(int e=E;e>=0;--e){cerr<<"jss["<<e<<"] = ";pv(jss[e],jss[e]+N);}
  
  below = Csid;
  for (int j = N; --j >= 1; ) {
    const int u = hld.sid[j];
    if (hld.head[u] != u) {
      below[j - 1] |= below[j];
    }
  }
}

Int query(int X, int Y, int M) {
// cerr<<COLOR("33")<<"query "<<X<<" "<<Y<<" "<<M<<COLOR()<<endl;
  vector<pair<int, int>> ps;
  hld.doPath(X, Y, true, [&](int jL, int jR) -> void {
    ps.emplace_back(jL, jR);
  });
  sort(ps.begin(), ps.end());
// cerr<<"ps = "<<ps<<endl;
  
  int csLen = 0, cRsLen = 0;
  static int cs[1010], cRs[1010];
  
  Int ans = 0;
  for (int e = E; --e >= 0; ) {
    ans |= 1LL << e;
    cRsLen = 0;
    if ([&]() -> bool {
      int cnt = 0;
      for (int i = 0; i < csLen; ++i) {
        if (!(ans & ~cs[i])) {
          if (++cnt >= M) {
            return true;
          }
        }
      }
      const Int ansR = ans + (1LL << e);
      const int posL = partition_point(jss[e], jss[e] + N, [&](int j) -> bool { return (Csid[j] < ans); }) - jss[e];
      const int posR = partition_point(jss[e], jss[e] + N, [&](int j) -> bool { return (Csid[j] < ansR); }) - jss[e];
      for (const auto &p : ps) {
        if (ans & ~below[p.first]) {
          continue;
        }
        for (int pos = lower_bound(jss[e] + posL, jss[e] + posR, p.first) - jss[e]; pos < posR; ++pos) {
          const int j = jss[e][pos];
          if (j >= p.second) break;
          // const Int c = Csid[j];
          // assert(!(ans & ~c));
          if (++cnt >= M) {
            return true;
          }
          cRs[cRsLen++] = Csid[j];
        }
      }
      return false;
    }()) {
// cerr<<"OK e = "<<e<<": cs = "<<cs<<endl;
      for (int i = 0; i < csLen; ++i) {
        if (ans & ~cs[i]) {
          swap(cs[i], cs[csLen - 1]);
          --csLen;
          --i;
        }
      }
    } else {
      ans &= ~(1LL << e);
      for (int i = 0; i < cRsLen; ++i) {
        cs[csLen++] = cRs[i];
      }
    }
  }
// cerr<<ps.size()<<" ";
  return ans;
}

int main() {
  for (; ~scanf("%d", &N); ) {
    A.resize(N - 1);
    B.resize(N - 1);
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
    }
    C.resize(N);
    for (int u = 0; u < N; ++u) {
      scanf("%lld", &C[u]);
    }
    scanf("%d", &Q);
    
    build();
    
    Int lastans = 0;
    for (int q = 0; q < Q; ++q) {
      Int X, Y;
      int M;
      scanf("%lld%lld%d", &X, &Y, &M);
      X = (X ^ lastans) % N + 1;
      Y = (Y ^ lastans) % N + 1;
      --X;
      --Y;
      assert(0 <= X); assert(X < N);
      assert(0 <= Y); assert(Y < N);
      
      const Int ans = query(X, Y, M);
      printf("%lld\n", ans);
#ifdef LOCAL
if(N==1'000'000)continue;
#endif
      lastans = ans;
    }
  }
  return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 0ms
memory: 130928kb

input:

931
184 700
485 184
419 485
386 419
308 386
114 308
301 114
598 301
120 598
144 120
595 144
812 595
236 812
7 236
543 7
327 543
858 327
68 858
177 68
398 177
899 398
408 899
848 408
202 848
269 202
304 269
540 304
647 540
672 647
314 672
157 314
241 157
745 241
300 745
343 300
92 343
117 92
30 117
2...

output:

1152921504606846976

result:

ok 1 number(s): "1152921504606846976"

Test #2:

score: -5
Wrong Answer
time: 3ms
memory: 131060kb

input:

915
911 748
514 911
805 514
729 805
753 729
40 753
671 40
664 671
94 664
61 94
726 61
690 726
597 690
216 597
644 216
533 644
605 533
22 605
307 22
455 307
377 455
114 377
660 114
589 660
569 589
409 569
408 409
821 408
736 821
599 736
60 599
475 60
57 475
412 57
85 412
524 85
846 524
595 846
262 59...

output:

288230376151711744

result:

wrong answer 1st numbers differ - expected: '288230376151711752', found: '288230376151711744'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 10
Accepted

Test #17:

score: 10
Accepted
time: 27ms
memory: 174696kb

input:

99115
98506 98914
1961 98506
45808 1961
23027 45808
16655 23027
66393 16655
77250 66393
68284 77250
53684 68284
21189 53684
84955 21189
73464 84955
47574 73464
40651 47574
21101 40651
6589 21101
59680 6589
6185 59680
25529 6185
207 25529
33286 207
98459 33286
92565 98459
85446 92565
97388 85446
1630...

output:

2050

result:

ok 1 number(s): "2050"

Test #18:

score: 0
Accepted
time: 49ms
memory: 178844kb

input:

99546
79711 12863
50539 79711
13393 50539
27933 13393
13465 27933
79157 13465
53742 79157
51081 53742
32220 51081
21079 32220
85595 21079
50222 85595
14565 50222
4589 14565
13763 4589
58913 13763
93835 58913
34953 93835
2185 34953
10246 2185
64420 10246
44274 64420
63093 44274
8007 63093
85947 8007
...

output:

512

result:

ok 1 number(s): "512"

Test #19:

score: 0
Accepted
time: 35ms
memory: 176992kb

input:

99762
90013 76047
42293 90013
7801 42293
75274 7801
59320 75274
60896 59320
10435 60896
5384 10435
34648 5384
15596 34648
92041 15596
67457 92041
20760 67457
65611 20760
81462 65611
38984 81462
17583 38984
83787 17583
59980 83787
71477 59980
31143 71477
92168 31143
71205 92168
69348 71205
6111 69348...

output:

16386

result:

ok 1 number(s): "16386"

Test #20:

score: 0
Accepted
time: 49ms
memory: 173172kb

input:

99132
46469 40521
51811 46469
47968 51811
10584 47968
73 10584
27351 73
16693 27351
12495 16693
53425 12495
95973 53425
24901 95973
82771 24901
49155 82771
35995 49155
50432 35995
91209 50432
5781 91209
83457 5781
41361 83457
37973 41361
48829 37973
62896 48829
77593 62896
21307 77593
86547 21307
61...

output:

8194

result:

ok 1 number(s): "8194"

Test #21:

score: 0
Accepted
time: 42ms
memory: 176440kb

input:

99403
81802 91324
60321 81802
76749 60321
70097 76749
16085 70097
8301 16085
61886 8301
72994 61886
23906 72994
18815 23906
6781 18815
7774 6781
18318 7774
54769 18318
39330 54769
55677 39330
46758 55677
36164 46758
10159 36164
24678 10159
29603 24678
14941 29603
7966 14941
42934 7966
35909 42934
24...

output:

32770

result:

ok 1 number(s): "32770"

Test #22:

score: 0
Accepted
time: 40ms
memory: 176552kb

input:

99468
33859 68644
12306 33859
44304 12306
18200 44304
27325 18200
35907 27325
88149 35907
71599 88149
86384 71599
83793 86384
19513 83793
4843 19513
3007 4843
52878 3007
83019 52878
5275 83019
61517 5275
21453 61517
55993 21453
50710 55993
16211 50710
76061 16211
12048 76061
41970 12048
86181 41970
...

output:

514

result:

ok 1 number(s): "514"

Test #23:

score: 0
Accepted
time: 35ms
memory: 172300kb

input:

99179
45430 91876
8718 45430
75718 8718
15306 75718
21806 15306
78221 21806
74287 78221
66218 74287
66830 66218
64948 66830
16118 64948
33879 16118
81821 33879
69640 81821
27802 69640
25979 27802
6393 25979
63447 6393
48459 63447
53612 48459
27525 53612
52654 27525
80810 52654
767 80810
23808 767
82...

output:

32768

result:

ok 1 number(s): "32768"

Test #24:

score: 0
Accepted
time: 37ms
memory: 172544kb

input:

99240
8561 98467
49571 8561
13264 49571
94195 13264
85879 94195
53012 85879
29828 53012
25813 29828
57793 25813
10678 57793
88525 10678
70070 88525
54163 70070
51466 54163
3857 51466
77958 3857
29023 77958
154 29023
5173 154
4349 5173
24310 4349
21821 24310
36125 21821
75498 36125
7147 75498
22336 7...

output:

32770

result:

ok 1 number(s): "32770"

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Wrong Answer

Test #45:

score: 0
Wrong Answer
time: 1761ms
memory: 363308kb

input:

996678
2 1
3 1
4 1
5 1
6 3
7 5
8 5
9 5
10 7
11 8
12 9
13 1
14 2
15 7
16 4
17 5
18 17
19 16
20 2
21 1
22 1
23 9
24 17
25 19
26 10
27 9
28 7
29 25
30 25
31 4
32 11
33 31
34 21
35 13
36 19
37 25
38 10
39 11
40 20
41 35
42 1
43 19
44 20
45 41
46 1
47 19
48 5
49 28
50 21
51 33
52 7
53 14
54 21
55 20
56 1...

output:

4
0
4
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
8
0
0
0
0
16
0
0
4096
0
0
0
0
4096
0
0
0
0
2
0
0
0
0
4
0
0
0
0
32
64
0
0
0
512
64
4
4096
0
2
0
0
131072
0
0
0
0
0
0
0
0
2
0
0
0
2
0
4096
2
0
0
0
0
0
512
2
8
0
0
4096
64
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
512
0
0
36
0
0
0
0
0
0
0
64
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

wrong answer 1467th numbers differ - expected: '4294967298', found: '4294967296'

Subtask #8:

score: 0
Skipped

Dependency #1:

0%