QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386113#8575. Three Person Tree Gamehos_lyricAC ✓61ms36664kbC++147.4kb2024-04-11 12:15:102024-04-11 12:15:11

Judging History

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

  • [2024-04-11 12:15:11]
  • 评测
  • 测评结果:AC
  • 用时:61ms
  • 内存:36664kb
  • [2024-04-11 12:15:10]
  • 提交

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 <random>
#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);
  }
};

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


int N;
int A, B, C;
vector<int> U, V;

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d", &N);
    scanf("%d%d%d", &A, &B, &C);
    --A;
    --B;
    --C;
    U.resize(N - 1);
    V.resize(N - 1);
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d", &U[i], &V[i]);
      --U[i];
      --V[i];
    }
    
    Hld hld(N);
    for (int i = 0; i < N - 1; ++i) {
      hld.ae(U[i], V[i]);
    }
    hld.build(A);
    const int L = hld.lca(B, C);
    const int a = hld.dep[L];
    const int b = hld.dep[B] - a;
    const int c = hld.dep[C] - a;
// cerr<<hld<<a<<" "<<b<<" "<<c<<endl;
    
    string ans;
    if (a + c == 1 || (a < b && a <= c + 1)) ans += "A";
    if (b < c && b <= a) ans += "B";
    if (c < a - 1 && c <= b) ans += "C";
    if (ans == "") ans += "DRAW";
    puts(ans.c_str());
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3700kb

input:

2
3
1 2 3
2 1
3 1
4
1 2 3
1 4
2 4
3 4

output:

A
DRAW

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 23ms
memory: 3996kb

input:

10000
20
2 12 1
16 15
3 2
16 17
14 13
11 12
9 8
10 9
18 17
6 5
18 19
13 12
5 4
7 6
20 19
14 15
3 4
11 10
1 2
8 7
20
12 13 1
18 13
12 11
19 15
17 16
10 14
4 2
15 11
6 5
3 2
4 13
20 8
11 9
3 7
14 16
5 8
5 4
9 6
10 3
1 2
17
2 17 15
9 10
5 4
9 8
2 11
6 7
8 7
13 4
2 3
6 15
5 6
17 8
2 1
3 4
16 7
14 5
3 12...

output:

A
B
C
B
DRAW
C
A
A
A
DRAW
C
B
B
B
DRAW
A
DRAW
A
C
DRAW
A
B
A
A
A
B
B
B
C
A
A
A
B
B
DRAW
C
DRAW
A
A
A
A
A
B
B
A
C
DRAW
A
B
A
B
DRAW
A
C
DRAW
A
B
C
DRAW
DRAW
A
A
A
DRAW
DRAW
B
B
B
A
DRAW
B
B
A
A
DRAW
B
A
A
B
DRAW
A
B
A
C
DRAW
A
B
A
A
A
B
B
B
A
A
B
B
A
C
DRAW
B
A
B
A
A
A
C
A
A
DRAW
A
A
C
A
DRAW
C
A
B
A...

result:

ok 10000 lines

Test #3:

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

input:

100
2000
455 1301 981
1508 1509
1242 1243
1261 1260
190 191
1981 1980
591 592
1792 1791
1726 1727
959 960
134 135
1193 1192
836 835
1803 1804
1577 1578
1548 1549
718 717
1294 1295
1116 1117
59 58
138 139
425 426
1168 1169
1963 1962
1025 1026
867 866
892 893
589 588
871 872
891 892
722 721
1711 1712
...

output:

C
A
A
B
DRAW
C
A
B
B
DRAW
B
C
B
A
DRAW
B
C
A
C
DRAW
C
B
A
C
DRAW
A
C
C
C
DRAW
B
A
A
C
DRAW
C
A
B
C
DRAW
B
A
B
A
DRAW
A
C
B
A
DRAW
B
C
C
C
DRAW
A
B
B
C
DRAW
C
B
C
A
DRAW
A
C
B
A
DRAW
B
A
B
A
DRAW
C
A
C
B
DRAW
A
B
C
C
DRAW
C
B
C
A
DRAW
B
A
C
B
DRAW
A
A
A
C
DRAW

result:

ok 100 lines

Test #4:

score: 0
Accepted
time: 61ms
memory: 36664kb

input:

1
200000
123236 117321 150583
47722 47723
103604 103605
48192 48191
19204 19205
3666 3667
190708 190709
111542 111541
16125 16124
164298 164299
55406 55405
62042 62041
42100 42101
40664 40663
131742 131743
105518 105517
24249 24250
174387 174388
29840 29841
164536 164537
54802 54803
6378 6377
97486 ...

output:

A

result:

ok single line: 'A'

Test #5:

score: 0
Accepted
time: 51ms
memory: 21360kb

input:

1
200000
151854 28266 141391
178840 177656
70949 127572
92675 174074
38426 55569
16718 64264
72596 171817
36908 36081
44793 65081
114199 93358
10460 36725
18563 26764
77047 29901
17769 39712
109495 141203
24130 37855
165153 135141
94225 107789
57603 49313
197306 48518
61030 57058
199291 42676
60161 ...

output:

B

result:

ok single line: 'B'

Test #6:

score: 0
Accepted
time: 59ms
memory: 32704kb

input:

1
200000
107496 54564 62204
75611 75612
33562 133562
66786 66785
35079 35078
40044 40045
99675 199675
121963 21963
15671 15672
3062 103062
71627 171627
27125 127125
30049 30048
63164 63165
183373 83373
51319 51320
99879 199879
36383 136383
89110 89109
7607 107607
20098 20099
57792 157792
100415 415
...

output:

B

result:

ok single line: 'B'

Test #7:

score: 0
Accepted
time: 53ms
memory: 21360kb

input:

1
200000
158505 85726 178357
30247 29809
107160 107392
84411 84297
80963 81018
64893 65118
194706 194894
8253 8478
47677 48197
120341 120487
68388 68653
41048 40580
128093 127913
118156 117983
97582 97422
166508 166267
171977 171895
108683 108912
102410 102283
130584 130479
75441 75592
145257 145092...

output:

A

result:

ok single line: 'A'

Test #8:

score: 0
Accepted
time: 13ms
memory: 3700kb

input:

10992
3
1 2 3
2 1
3 1
3
1 3 2
2 1
3 1
3
2 1 3
2 1
3 1
3
2 3 1
2 1
3 1
3
3 1 2
2 1
3 1
3
3 2 1
2 1
3 1
4
1 2 3
2 1
3 2
4 1
4
1 2 4
2 1
3 2
4 1
4
1 3 2
2 1
3 2
4 1
4
1 3 4
2 1
3 2
4 1
4
1 4 2
2 1
3 2
4 1
4
1 4 3
2 1
3 2
4 1
4
2 1 3
2 1
3 2
4 1
4
2 1 4
2 1
3 2
4 1
4
2 3 1
2 1
3 2
4 1
4
2 3 4
2 1
3 2
4 ...

output:

A
A
B
A
B
A
B
A
A
A
A
A
A
B
A
A
A
A
A
B
B
B
C
A
B
B
A
B
A
C
A
A
A
A
A
A
B
B
A
DRAW
A
DRAW
B
B
A
DRAW
A
DRAW
B
B
A
DRAW
A
DRAW
B
A
A
A
A
A
A
A
B
A
A
A
A
B
B
A
A
A
A
A
B
A
A
C
A
B
B
B
B
B
C
A
B
C
A
C
B
B
A
A
B
A
A
C
A
A
A
A
B
B
A
C
B
A
C
C
A
B
B
B
B
A
A
A
A
A
A
A
A
A
A
A
A
B
B
A
A
A
A
A
DRAW
A
A
DRAW
...

result:

ok 10992 lines

Test #9:

score: 0
Accepted
time: 29ms
memory: 3980kb

input:

22222
9
1 2 3
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 4
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 5
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 6
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 7
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 8
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 9
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 3 2
2 1
3 ...

output:

B
B
B
A
A
A
A
A
B
B
A
A
A
A
A
C
B
A
A
A
A
A
C
C
A
A
A
A
A
A
A
A
B
B
B
A
A
A
A
A
B
B
A
A
A
A
A
C
B
A
A
A
A
A
C
C
A
A
A
B
B
B
B
A
B
B
A
A
A
A
A
A
B
A
A
A
A
A
A
C
A
A
A
A
A
A
A
A
B
B
B
A
A
A
A
C
B
B
A
A
A
A
C
C
B
A
A
A
A
C
C
C
A
A
A
B
B
B
B
B
A
A
B
B
B
B
A
A
B
A
A
A
A
A
A
A
A
A
A
A
C
A
A
A
B
B
B
C
A
A
...

result:

ok 22222 lines

Extra Test:

score: 0
Extra Test Passed