QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90696#5828. 游戏dispensable100 ✓781ms104368kbC++146.6kb2023-03-24 19:42:212023-03-24 19:42:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-24 19:42:22]
  • 评测
  • 测评结果:100
  • 用时:781ms
  • 内存:104368kb
  • [2023-03-24 19:42:21]
  • 提交

answer

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fir first
#define sec second
using namespace std;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
const int MAXN = 400010;
int N, Q;
int tot, head[MAXN];
struct Edge {
    int to, nxt;
} edge[MAXN];
void add(int u, int v) {
    edge[++tot].to = v, edge[tot].nxt = head[u]; head[u] = tot;
}
int fa[MAXN][21], dep[MAXN], son[MAXN], len[MAXN];
void dfs(int u, int father) {
    fa[u][0] = father, dep[u] = dep[father] + 1;
    for (int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int e = head[u]; e; e = edge[e].nxt) {
        int v = edge[e].to;
        if (v == father) continue;
        dfs(v, u); 
        if (len[u] < len[v] + 1) {
            len[u] = len[v] + 1;
            son[u] = v;
        }
    }
}
int dfn[MAXN], rnk[MAXN], dfncnt;
void Dfs(int u, int father) {
    rnk[dfn[u] = ++dfncnt] = u;
    if (son[u]) Dfs(son[u], u);
    for (int e = head[u]; e; e = edge[e].nxt) {
        int v = edge[e].to;
        if (v != father and v != son[u]) 
            Dfs(v, u);
    }
}
int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20; i >= 0; i--)
        if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    if (x == y) return x;
    for (int i = 20; i >= 0; i--) 
        if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}
int dis(int x, int y) {
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
int f[MAXN][4], to[MAXN][4];
void dfs1(int u, int father) {
    vector<pii>D; 
    D.emplace_back(0, u), D.emplace_back(0, u), D.emplace_back(0, u);
    for (int e = head[u]; e; e = edge[e].nxt) {
        int v = edge[e].to;
        if (v == father) continue;
        dfs1(v, u); D.emplace_back(f[v][0] + 1, v);
    }
    sort(D.begin(), D.end(), [](pii x, pii y) {
        return x.fir > y.fir;
    });
    for (int i = 0; i < 3; i++)
        f[u][i] = D[i].fir, to[u][i] = D[i].sec;
}
void dfs2(int u, int father) {
    if (!father) f[u][3] = 0, to[u][3] = u;
    else {
        f[u][3] = f[father][3] + 1, to[u][3] = to[father][3];
        if (f[father][0] == f[u][0] + 1) {
            if (f[u][3] < f[father][1] + 1)
                f[u][3] = f[father][1] + 1, to[u][3] = to[father][1];
        } else {
            if (f[u][3] < f[father][0] + 1)
                f[u][3] = f[father][0] + 1, to[u][3] = to[father][0];
        }
    }
    for (int e = head[u]; e; e = edge[e].nxt) {
        int v = edge[e].to;
        if (v == father) continue;
        dfs2(v, u);
    }
}
struct Query {
    int x, y, z;
} q[MAXN];
struct Node {
    int opt, x, y, z, tim;
} a[MAXN], b[MAXN];
int aans[MAXN];
vector<Query>query[MAXN];
void cdq(int l, int r) {
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int L = l, R = mid + 1, cnt = l, Max = 0;
    while (L <= mid and R <= r) {
        if (a[L].y > a[R].y or (a[L].y == a[R].y and a[L].z >= a[R].z)) {
            if (a[L].opt == 1) 
                if (a[Max].z <= a[L].z) Max = L;
            b[cnt++] = a[L++];
        }
        else {
            if (a[R].opt == 2) 
                if (a[R].z <= a[Max].z) aans[a[R].tim] = a[Max].tim;
            b[cnt++] = a[R++];
        }
    }
    while (R <= r) {
        if (a[R].opt == 2)
            if (a[R].z <= a[Max].z) aans[a[R].tim] = a[Max].tim;
        b[cnt++] = a[R++];
    }
    while (L <= mid) 
        b[cnt++] = a[L++];
    for (int i = l; i <= r; i++) a[i] = b[i];
}
int jump(int x, int step) {
    for (int i = 20; i >= 0; i--)
        if ((step >> i) & 1) x = fa[x][i];
    return x;
}
int ans[MAXN][3], Ans[MAXN][3];
int main() {
    N = read();
    for (int i = 1; i < N; i++) {
        int u = read(), v = read();
        add(u, v), add(v, u);
    }
    dfs(1, 0), Dfs(1, 0);
    dfs1(1, 0), dfs2(1, 0);
    for (int i = 1; i <= N; i++) {
        vector<pii>D; D.clear();
        for (int j = 0; j <= 3; j++) D.emplace_back(f[i][j], to[i][j]);
        sort(D.begin(), D.end(), [](pii x, pii y) {
            return x.fir > y.fir;
        });
        for (int j = 0; j <= 2; j++) f[i][j] = D[2 - j].fir, to[i][j] = D[2 - j].sec;
    }
    for (int i = 1; i <= N; i++)
        a[i] = (Node) { 1, f[i][0], f[i][1], f[i][2], i };
    Q = read();
    for (int i = 1; i <= Q; i++) {
        int x = read(), y = read(), z = read(); static int p[3]; q[i] = (Query) {x, y, z};
        p[0] = (y + z - x) / 2, p[1] = (x + z - y) / 2, p[2] = (x + y - z) / 2;
        sort(p, p + 3);
        a[N + i] = (Node) { 2, p[0], p[1], p[2], i };
    }
    sort(a + 1, a + N + Q + 1, [](Node x, Node y) {
        return x.x != y.x ? x.x > y.x : (x.y != y.y ? x.y > y.y : (x.z != y.z ? x.z > y.z : x.opt < y.opt));
    });
    a[0] = (Node) { 1, -1, -1, -1, 0 };
    cdq(1, N + Q);
    for (int i = 1; i <= Q; i++) {
        assert(aans[i]);
        int u = aans[i]; static int p[4];
        int x = q[i].x, y = q[i].y, z = q[i].z;
        p[0] = (y + z - x) / 2, p[1] = (x + z - y) / 2, p[2] = (x + y - z) / 2;
        sort(p, p + 3);
        for (int j = 0; j <= 2; j++) {
            if (p[j] == 0) {
                ans[i][j] = u;
                continue;
            } 
            if (fa[to[u][j]][0] == u) {
                ans[i][j] = rnk[dfn[to[u][j]] + p[j] - 1];
            } else {
                if (dep[u] - dep[to[u][j]] == f[u][j]) {
                    ans[i][j] = jump(u, p[j]);               
                } else {
                    int v = fa[to[u][j]][0];
                    if (dep[u] - dep[v] >= p[j])
                        ans[i][j] = jump(u, p[j]);
                    else
                        ans[i][j] = rnk[dfn[to[u][j]] + p[j] - (dep[u] - dep[v]) - 1];
                }
            }
        }
        for (int j = 0; j <= 2; j++) p[j] = j;
        do {
            bool flag = true;
            flag &= dis(ans[i][p[0]], ans[i][p[1]]) == x;
            flag &= dis(ans[i][p[0]], ans[i][p[2]]) == y;
            flag &= dis(ans[i][p[1]], ans[i][p[2]]) == z;
            if (flag) {
                for (int j = 0; j <= 2; j++)
                    Ans[i][j] = ans[i][p[j]];
                break;
            }
            //cerr << p[0] << " " << p[1] << " " << p[2] << "\n";
        } while (next_permutation(p, p + 3));
    }
    for (int i = 1; i <= Q; i++) {
        for (int j = 0; j <= 2; j++)
            printf("%d ", Ans[i][j]);
        printf("\n");
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 0ms
memory: 13112kb

input:

500
279 196
182 105
400 14
278 217
198 411
379 318
120 421
314 95
437 325
23 433
71 485
192 154
90 224
180 71
328 93
183 101
404 349
223 285
492 100
366 480
29 328
200 448
365 156
226 231
129 167
246 273
171 452
284 6
131 471
229 90
480 48
448 157
240 221
7 36
401 200
255 438
436 110
281 489
388 258...

output:

241 295 342 
201 280 94 
40 94 295 
126 480 101 
297 386 305 
116 376 424 
241 30 84 
261 292 360 
248 297 346 
132 60 87 
366 360 427 
183 74 270 
74 376 390 
124 342 399 
108 211 295 
360 200 427 
477 60 431 
60 417 476 
62 417 110 
17 48 219 
64 68 476 
110 298 331 
68 399 332 
179 70 168 
123 16...

result:

ok Accepted!

Test #2:

score: 10
Accepted
time: 8ms
memory: 13676kb

input:

2000
643 1871
689 23
1822 1443
1031 1027
1655 845
189 771
1561 498
19 1778
576 1080
904 717
1690 291
1387 1077
398 811
1310 1231
645 1291
480 927
330 170
1464 1057
1033 894
1308 288
1292 1529
1212 122
1108 401
89 1118
1058 1088
1764 1314
981 1255
1893 864
180 1887
1903 843
734 1412
883 1013
1739 124...

output:

1093 1686 1733 
474 546 688 
1425 1528 1329 
308 1144 1686 
809 1887 758 
1501 128 892 
798 1262 1738 
1065 1784 418 
965 1788 386 
1329 979 1383 
749 1695 765 
867 1070 1338 
1717 232 793 
216 1091 1556 
886 1091 895 
894 758 1798 
109 758 1887 
608 506 1830 
393 1118 86 
597 1105 134 
466 1703 189...

result:

ok Accepted!

Test #3:

score: 10
Accepted
time: 148ms
memory: 52008kb

input:

200000
56968 132021
105656 107536
123627 58349
119191 138198
133708 142638
114350 24980
137784 40346
124158 130204
80684 183207
78156 94449
21893 157560
54464 73571
145830 57756
160288 32120
178632 142663
26565 185985
70576 24906
32217 115826
185756 137673
54280 179613
77826 144447
66005 29955
11745...

output:

34526 187920 126136 

result:

ok Accepted!

Test #4:

score: 10
Accepted
time: 165ms
memory: 52020kb

input:

200000
41999 100683
85781 129266
122431 179332
162416 44814
24405 42267
154161 12483
178049 159964
67625 152391
133072 25866
178005 14695
94384 170290
54701 40323
66280 128515
159022 55057
14985 12920
182805 40659
173117 67973
99771 26102
198919 94543
23608 187601
61125 5759
89437 47647
18142 192402...

output:

124016 118230 38009 

result:

ok Accepted!

Test #5:

score: 10
Accepted
time: 170ms
memory: 52332kb

input:

200000
195072 75458
31991 127114
60943 49502
186375 1130
45394 147217
168455 84307
132752 188952
101108 130004
107490 22003
16275 187645
111002 42669
138880 137115
112688 172751
81697 99037
166996 18495
2234 56119
170807 101349
105736 23180
148159 40863
136678 11849
190707 91245
61779 120740
157115 ...

output:

86732 82102 128046 
88430 178958 77240 
152222 8229 88432 
82637 19743 158643 
2255 55912 104975 
82263 198593 109139 
57427 140014 194500 
116081 34080 51401 
102355 132383 56487 
190535 171087 78434 

result:

ok Accepted!

Test #6:

score: 10
Accepted
time: 170ms
memory: 52096kb

input:

200000
48556 78408
155026 9376
8983 61211
150393 85068
90892 109283
75746 89742
6760 187245
168658 130735
68602 127646
60802 149828
22898 59471
172845 100274
42303 190696
7612 134905
94702 59800
129633 192496
19903 64869
51318 63358
34692 66030
98535 176606
153647 177529
157903 147292
106273 107278
...

output:

78196 24538 195329 
61656 110387 9495 
116888 61263 21725 
137515 39144 152524 
195824 177152 19728 
102804 84168 108282 
35006 110558 27213 
100096 93881 177689 
62609 105097 127333 
64257 48141 90870 

result:

ok Accepted!

Test #7:

score: 10
Accepted
time: 667ms
memory: 104368kb

input:

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

output:

40974 186618 123670 
198128 168325 129369 
73546 189029 168325 
168325 148214 184995 
132350 173980 168325 
81840 168325 196455 
142430 198601 83817 
10055 87683 181923 
184756 10467 142430 
189288 168325 14101 
171224 168325 28684 
107964 168325 190036 
172352 151770 168325 
180966 87683 3728 
7729...

result:

ok Accepted!

Test #8:

score: 10
Accepted
time: 350ms
memory: 67644kb

input:

200000
5732 55198
128966 25317
114737 116391
150003 18274
43867 70745
76222 4169
55976 114951
198396 72896
38647 19711
12756 172119
73197 117994
117512 14177
130965 126990
119440 183341
142023 60829
111893 57350
122754 123305
36525 79077
36447 91967
135405 170456
165839 147481
66074 175822
22238 264...

output:

178310 178310 183543 
178310 178310 98115 
178310 178310 36778 
178310 178310 30537 
178310 178310 169883 
178310 178310 65826 
178310 178310 31265 
178310 178310 161066 
178310 178310 129717 
178310 178310 85 
178310 178310 98442 
178310 178310 118809 
178310 178310 183881 
178310 178310 87348 
178...

result:

ok Accepted!

Test #9:

score: 10
Accepted
time: 781ms
memory: 67532kb

input:

200000
185063 17064
180987 114492
88071 71803
158363 135918
60910 54848
97338 6734
192937 9410
49617 199068
82499 63554
188791 188152
178767 40866
11304 27212
144234 138097
42236 3946
103355 12683
50992 20598
145723 48620
11709 115688
123172 121379
70541 130844
147827 39431
139372 61280
42705 54015
...

output:

174856 71977 179574 
3000 92997 150200 
131745 178675 129413 
8059 130361 28875 
37393 59391 45678 
42489 185493 12143 
66024 107670 120658 
10044 8498 121963 
154803 72889 112576 
82106 34224 127016 
63867 80406 46292 
163519 91560 155503 
98542 88190 168671 
13820 79772 56998 
193797 136088 78237 ...

result:

ok Accepted!

Test #10:

score: 10
Accepted
time: 732ms
memory: 67412kb

input:

200000
197244 185999
18639 124754
154223 12099
53676 167616
22710 22294
150412 66132
19320 75478
170410 122661
130961 175554
171586 85572
188386 81238
120249 117687
43214 126266
8744 165654
164725 189519
124144 170329
86605 100197
130545 17030
113301 96665
67733 187286
37846 146399
75352 117550
3235...

output:

135279 172309 119889 
91745 39778 86165 
174795 48231 61661 
45021 101167 129885 
129807 175058 144479 
192745 159146 67647 
27117 17150 39942 
187426 29159 22043 
33903 148821 19178 
33905 3886 131706 
132582 157902 165252 
90388 100828 120122 
74622 10772 21901 
23433 20382 11390 
95136 59440 7634...

result:

ok Accepted!

Extra Test:

score: 0
Extra Test Passed