QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#864493#5020. 举办乘凉州喵,举办乘凉州谢谢喵cooluo8 1000ms217080kbC++2310.2kb2025-01-20 17:26:232025-01-20 17:26:30

Judging History

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

  • [2025-01-20 17:26:30]
  • 评测
  • 测评结果:8
  • 用时:1000ms
  • 内存:217080kb
  • [2025-01-20 17:26:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ul unsigned ll
#define LL __int128_t
#define db double
#define DB long db
#define pii pair<int, int>
#define fi first
#define se second
#define mkpr make_pair
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define rsz resize
#define eb emplace_back
#define all(c) (c).begin(), (c).end()
#define bit(k) (1 << (k))
#define Bit(k) (1ll << (k))
#define BIT(k) ((LL)1 << (k))
#define lowbit(x) ((x) & -(x))
#define bin(s, k) ((s) >> (k) & 1)
#define lg2(x) (31 - __builtin_clz(x))
#define LG2(x) (63 - __builtin_clzll(x))
#define popcnt(x) __builtin_popcount(x)
#define mem(a, x) memset(a, x, sizeof(a))
#define req(i, l, r) for (int i(l), i##End(r); i < i##End; i = -~i)
#define rep(i, l, r) for (int i(l), i##End(r); i <= i##End; i = -~i)
#define per(i, r, l) for (int i(r), i##End(l); i >= i##End; i = ~-i)

// #define FILERR

#ifdef JYR
#ifdef FILERR
auto filerr = fopen("Test.err", "w");
#else
auto filerr = stderr;
#endif
#define errs(x) fputs(x "\n", filerr)
#define errm(x, ...) fprintf(filerr, x, ##__VA_ARGS__)
#else
#define errs(x) 0
#define errm(x, ...) 0
#endif

template<typename T, typename U> void chkmx(T &_a, U _b) { if (_a < _b) _a = _b; }
template<typename T, typename U> void chkmn(T &_a, U _b) { if (_b < _a) _a = _b; }

bool Mbe;

struct FastIO {
    char buf[1 << 20], *p1, *p2;
    char puf[1 << 20], *pf;

    FastIO() : p1(buf), p2(buf), pf(puf) {}
    ~FastIO() { fwrite(puf, 1, pf - puf, stdout); }

    char gc() {
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin);
        return p1 == p2 ? EOF : *p1++;
    }

    bool blank(char c) { return c == ' ' || c == '\r' || c == '\n' || c == '\t'; }

    char rd() {
        char c = gc(); while (blank(c)) c = gc();
        return c;
    }

    template<typename T> T rd() {
        T x = 0; int f = 0; char c = gc();
        while (!isdigit(c)) f = (c == '-'), c = gc();
        while (isdigit(c)) x = (x << 1) + (x << 3) + (c - '0'), c = gc();
        return f ? -x : x;
    }

    int rds(char *s) {
        char c = gc(), *S = s;
        while (blank(c)) c = gc();
        while (!blank(c) && c != EOF) *s++ = c, c = gc();
        return *s = 0, abs(s - S);
    }

    int rdl(char *s) {
        char c = gc(), *S = s;
        while (c == '\r' || c == '\n') c = gc();
        while (c != '\r' && c != '\n' && c != EOF) *s++ = c, c = gc();
        return *s = 0, abs(s - S);
    }

    void rd(char &c) { c = rd(); }

    void rd(char *s) {
        char c = gc();
        while (blank(c)) c = gc();
        if (c == EOF) { *s = 0; return; }
        while (!blank(c) && c != EOF) *s++ = c, c = gc();
        *s = 0;
    }

    template<typename T> void rd(T &x) {
        x = 0; int f = 0; char c = gc();
        while (!isdigit(c)) f = (c == '-'), c = gc();
        while (isdigit(c)) x = (x << 1) + (x << 3) + (c - '0'), c = gc();
        if (f) x = -x;
    }

    template<typename T, typename... Ts>
    void rd(T& x, Ts&... xs) { rd(x), rd(xs...); }

    void pc(const char &c) {
        if (pf - puf == 1 << 20) fwrite(pf = puf, 1, 1 << 20, stdout);
        *pf++ = c;
    }

    void prt(char c) { pc(c); }
    void prt(char* s) { while (*s) pc(*s++); }
    void prt(const char* s) { while (*s) pc(*s++); }

    template<typename T> void prt(T x) {
        static int st[41], tp = 0;
        if (x == 0) { pc('0'); return; }
        if (x < 0) x = -x, pc('-');
        while (x) st[++tp] = x % 10, x /= 10;
        while (tp) pc(st[tp--] + '0');
    }

    template<typename T> void prt(T *x) { while (*x) pc(*x++); }

    template<typename T, typename... Ts>
    void prt(T x, Ts... xs) { prt(x), prt(xs...); }

    void prts(const char *s, char c = '\n') {
        while (*s) pc(*s++);
        if (c) pc(c);
    }
} IO;

#define rd IO.rd
#define rdl IO.rdl
#define ri rd<int>()
#define rl rd<ll>()
#define prt IO.prt
#define prs IO.prts
#define edl IO.pc('\n')

// #define MC

#define N 200005
#define mod 998244353
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

int n, m, q, R, X, S;
vi G[N];
int fa[N], de[N], sz[N], sn[N];
int tp[N], df[N], nf[N], ed[N], tt;
vii ve[N], vc[N], vt[N], vo[N], vr[N];
int mx[N] = {inf};
int ans[N];
bool vs[N];

struct BITree {
    int sz;
    vector<int> vt;

    void rsz(int _sz = n) {
        sz = _sz + 1;
        vt = vector<int>(sz + 1, 0);
    }

    void mdf(int p, int k) {
        assert(++p > 0);
        for (int i = p; i <= sz; i += lowbit(i))
            vt[i] += k;
    }

    int qry(int p) {
        if (++p < 0) return 0;
        chkmn(p, sz);
        int res = 0;
        for (int i = p; i; i -= lowbit(i))
            res += vt[i];
        return res;
    }
} T[N << 1];

struct bitree {
    int s[N];

    void mdf(int p, int k) {
        for (int i = max(p, 0); i <= n; i += lowbit(i))
            s[i] += k;
    }

    int qry(int p) {
        int res = 0;
        for (int i = min(p, n); i; i -= lowbit(i))
            res += s[i];
        return res;
    }
} tk;

void dfs1(int u, int ft) {
    de[u] = de[fa[u] = ft] + (sz[u] = 1);
    for (auto v : G[u]) if (v != ft) {
        dfs1(v, u), sz[u] += sz[v];
        if (sz[sn[u]] < sz[v]) sn[u] = v;
    }
}

void dfs2(int u, int ft) {
    tp[u] = ft, nf[df[u] = ed[u] = ++tt] = u;
    if (!sn[u]) return; dfs2(sn[u], ft);
    for (auto v : G[u]) if (v != fa[u] && v != sn[u]) dfs2(v, v);
    ed[u] = tt;
}

int lca(int u, int v) {
    while (tp[u] != tp[v]) de[tp[u]] > de[tp[v]] ? u = fa[tp[u]] : v = fa[tp[v]];
    return de[u] < de[v] ? u : v;
}

void bld(int u) {
    int rt = 0, s = sz[u];
    function<void(int, int)> fdrt = [&](int u, int ft) {
        sz[u] = 1, mx[u] = 0;
        for (auto v : G[u]) if (!vs[v] && v != ft)
            fdrt(v, u), sz[u] += sz[v], chkmx(mx[u], sz[v]);
        chkmx(mx[u], s - sz[u]);
        if (mx[rt] > mx[u]) rt = u;
    }; fdrt(u, 0);
    int tu = ++m, du = 0;
    ve[rt].eb(0, tu);
    for (auto v : G[rt]) if (!vs[v]) {
        int tv = ++m, dv = 0;
        function<void(int, int, int)> gtds = [&](int u, int ft, int D) {
            chkmx(du, D), chkmx(dv, D);
            ve[u].eb(D, tu), ve[u].eb(D, -tv);
            for (auto v : G[u]) if (!vs[v] && v != ft)
                gtds(v, u, D + 1);
        }; gtds(v, rt, 1), T[tv].rsz(dv);
    }
    T[tu].rsz(du), vs[rt] = 1;
    for (auto v : G[rt]) if (!vs[v]) bld(v);
}

int qry(int u, int x) {
    int res = 0;
    for (auto [d, _] : ve[u]) {
        int t = _ < 0 ? -1 : 1, i = abs(_);
        res += t * T[i].qry(x - d);
    }
    return res;
}

void dfs3(int u, int ft) {
    if (sn[u]) rep(i, ed[sn[u]] + 1, ed[u]) tk.mdf(de[nf[i]] - de[u], 1);
    for (auto [x, i] : vc[u]) ans[i] += tk.qry(x);
    for (auto [x, i] : vt[u]) ans[i] -= tk.qry(x);
    // errm("dfs3(%d, %d)\n", u, ft);
    // rep(i, 1, n) errm(" | %d", tk.qry(i) - tk.qry(i - 1)); errs(" |");
    // for (auto [x, i] : vc[u]) errm(" + [%d %d]\n", x, i);
    // for (auto [x, i] : vt[u]) errm(" - [%d %d]\n", x, i);
    for (auto v : G[u]) if (v != ft) dfs3(v, u);
    if (sn[u]) rep(i, ed[sn[u]] + 1, ed[u]) tk.mdf(de[nf[i]] - de[u], -1);
}

void dfs4(int u, int ft, bool fg) {
    if (sn[u]) {
        for (auto v : G[u]) if (v != ft && v != sn[u]) dfs4(v, u, 0);
        dfs4(sn[u], u, 1);
    }
    tk.mdf(de[u], 1);
    if (sn[u]) rep(i, ed[sn[u]] + 1, ed[u]) tk.mdf(de[nf[i]], 1);
    for (auto [x, i] : vo[u]) ans[i] += tk.qry(de[u] + x) - tk.qry(de[u] - 1);
    for (auto [x, i] : vr[u]) ans[i] -= tk.qry(de[u] + x) - tk.qry(de[u] - 1);
    // errm("dfs4(%d, %d, %d)\n", u, ft, fg);
    // rep(i, 1, n) errm(" | %d", tk.qry(i) - tk.qry(i - 1)); errs(" |");
    // for (auto [x, i] : vo[u]) errm(" + [%d %d]: [%d, %d]\n", x, i, de[u], de[u] + x);
    // for (auto [x, i] : vr[u]) errm(" - [%d %d]: [%d, %d]\n", x, i, de[u], de[u] + x);
    if (!fg) rep(i, df[u], ed[u]) tk.mdf(de[nf[i]], -1);
}

void mslv() {
    req(i, 1, n = ri) {
        int u, v; rd(u, v);
        G[u].eb(v), G[v].eb(u);
    }
    dfs1(1, 0), dfs2(1, 1), bld(1);
    rep(u, 1, n) for (auto [d, _] : ve[u])
        T[abs(_)].mdf(d, 1);
        
    rep(i, 1, q = ri) {
        int u, v, x; rd(u, v, x);
        int t = lca(u, v);
        if (x == 0) { ans[i] = de[u] - de[t] + de[v] - de[fa[t]]; continue; }
        ans[i] = qry(t, x) + max(de[u] - de[t] - x, 0) + max(de[v] - de[t] - x, 0);
        // errm("%d: %d\n", i, ans[i]);
        vc[u].eb(x, i), vt[u].eb(x - 1, i);
        vc[v].eb(x, i), vt[v].eb(x - 1, i);
        vt[t].eb(x, i), vc[t].eb(x - 1, i);
        vt[t].eb(x, i), vc[t].eb(x - 1, i);
        if (u != t) {
            vo[sn[u]].eb(x - 1, i);
            if (x > 1) vr[sn[u]].eb(x - 2, i);
        }
        if (v != t) {
            vo[sn[v]].eb(x - 1, i);
            if (x > 1) vr[sn[v]].eb(x - 2, i);
        }
        // errm("? %d %d\n", u, v);
        while (tp[u] != tp[v]) {
            // errm("! %d %d\n", u, v);
            if (de[tp[u]] < de[tp[v]]) swap(u, v);
            u = tp[u], vr[u].eb(x, i), vo[u].eb(x - 1, i);
            if (u = fa[u]; u != t && sn[u]) vo[sn[u]].eb(x, i), vr[sn[u]].eb(x - 1, i);
        }
    }
    dfs3(1, 0);
    dfs4(1, 0, 1);
    rep(i, 1, q) prt(ans[i]), edl;
}

/*















*/

void mprw() {}

bool Med;

int main() {
    #ifdef JYR
    errs("Running!");
    freopen("Test.in", "r", stdin);
    freopen("Test.out", "w", stdout);
    #endif
    mprw();
    #ifdef MC
    int _ = ri;
    while (_--) mslv();
    #else
    mslv();
    #endif
    errm("%.3lfMB %.0lfms\n", abs(&Med - &Mbe) / 1048576., clock() * 1000. / CLOCKS_PER_SEC);
    return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 13ms
memory: 25972kb

input:

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

output:

2859
1435
4976
178
158
3584
3622
1438
4974
1732
234
267
4581
255
4950
4976
4974
1470
4981
12
1379
4765
4974
4974
19
83
4950
4442
202
4864
374
3245
558
1113
218
2841
856
202
81
4768
2856
71
76
4207
4950
379
4811
4974
104
282
73
160
202
1393
4981
3530
103
2901
153
50
4864
410
4952
299
4614
2134
15
495...

result:

wrong answer 1st numbers differ - expected: '3226', found: '2859'

Subtask #2:

score: 8
Accepted

Test #9:

score: 8
Accepted
time: 709ms
memory: 129900kb

input:

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

output:

757
69428
2793
181264
91707
182
32496
199183
6399
15975
11640
119051
236
689
15
9532
41
36592
178936
56
45424
193403
90248
3417
949
68
34133
60471
199861
188090
75088
127
1
6
4
3
3
11
61157
199860
199153
155706
196287
192862
53742
51862
179199
428
196282
199989
3613
26
99007
134461
198159
20382
7518...

result:

ok 199996 numbers

Test #10:

score: 8
Accepted
time: 538ms
memory: 162100kb

input:

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

output:

22
31743
62
30
510
6079
94
24063
190
4079
382
30
62
12159
1022
2043
8063
62
4
3063
4079
30
254
46
10
22
6111
12159
16127
22
1
12031
1
94
382
766
4063
254
46
766
1022
62
766
1
22
46
30
8063
8063
254
3063
22
62
30
1
62
254
4
10
15871
1022
46
2039
6079
22
254
1022
16127
30
766
8127
14
14
10
46
1
62
406...

result:

ok 199995 numbers

Test #11:

score: 8
Accepted
time: 867ms
memory: 174920kb

input:

199993
25163 125238
125238 19096
19096 88864
88864 113505
113505 12722
12722 56225
56225 8736
8736 74926
74926 38529
38529 80231
80231 19719
19719 198784
198784 75213
75213 190174
190174 163340
163340 62363
62363 144160
144160 130912
130912 3919
3919 21218
21218 85281
85281 187312
187312 79930
79930...

output:

97095
57496
116181
132482
144412
69917
174677
96334
37980
80902
148979
22074
166530
153392
43419
163281
148526
62703
79363
199993
153733
152298
5085
156125
117973
61925
36346
95741
124148
102890
20093
5408
77598
176994
177809
169850
144418
43786
189237
69098
5167
199993
103575
105198
197612
38829
20...

result:

ok 199994 numbers

Test #12:

score: 8
Accepted
time: 887ms
memory: 205524kb

input:

200000
3219 118490
118490 61372
61372 74390
74390 88375
88375 63918
63918 37580
37580 33219
33219 170480
170480 81737
81737 153202
153202 93921
93921 149109
149109 88339
88339 167037
167037 67099
67099 58363
58363 6784
6784 109386
109386 11895
11895 14872
14872 65638
65638 43958
43958 181669
181669 ...

output:

59633
108235
72863
144596
90365
57521
48069
163045
124462
18633
39115
111210
59413
80420
86945
182373
99188
57011
148702
53778
132289
68037
69705
50797
91155
77852
27499
106082
87174
122445
78221
71755
10125
93101
163451
16175
104215
50130
81182
30091
44299
81429
91045
111890
73099
72278
74017
59177...

result:

ok 199992 numbers

Test #13:

score: 8
Accepted
time: 571ms
memory: 157784kb

input:

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

output:

40732
40074
40815
13444
89657
22422
23494
61358
102922
66209
62228
32272
77095
68562
27799
74336
45129
71632
68525
13022
71347
63735
92178
64200
90446
50728
83632
61441
43695
10496
35481
81587
75266
77943
56182
14188
46302
108160
84166
3192
52959
522
57676
28165
97982
15371
95012
3437
53633
49240
55...

result:

ok 199998 numbers

Test #14:

score: 8
Accepted
time: 516ms
memory: 182164kb

input:

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

output:

59224
71441
128293
104009
42824
136779
12532
93560
81095
108628
176617
63487
103752
175849
36193
178489
73311
34313
46423
75989
76344
145231
20076
127399
81148
17356
39455
99025
44904
3548
78503
135455
28
136931
58140
53161
33288
134084
67877
26048
51868
74301
139992
165315
126781
136117
28112
86333...

result:

ok 199996 numbers

Test #15:

score: 8
Accepted
time: 393ms
memory: 135824kb

input:

199997
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:

65710
203
400
304
388
328
441
19
417
49
311
329
193
71968
895
179
152645
282
7600
185
150933
150045
444
3693
56770
34420
8765
335
73751
4665
3
203
380
44479
392
356
113
373
46663
143312
234
265
386
378
339
184360
404
21904
9861
393
445
441
91
299
9
213
24586
65263
22235
121
35761
169
36121
435
40035...

result:

ok 199995 numbers

Test #16:

score: 8
Accepted
time: 851ms
memory: 139236kb

input:

199997
1 64008
2 4187
3 154904
4 191579
5 107782
6 29053
7 123085
8 191601
9 95335
10 164039
11 171804
12 145532
13 104884
14 19820
15 74055
16 14172
17 98802
18 144668
19 188276
20 173096
21 62815
22 133749
23 65035
24 161785
25 191028
26 84730
27 176488
28 173295
29 110316
30 121532
31 81037
32 81...

output:

135622
123942
47301
113894
93180
10469
9237
13166
2896
20323
182669
26483
168662
47202
7900
7785
129591
1577
17943
5638
16670
16980
32760
153668
394
142656
30298
1801
167880
25099
10860
39103
28660
158337
55
126816
57661
17387
11147
95051
3
13130
28040
163801
141
109445
110915
13173
56634
20527
6325...

result:

ok 199993 numbers

Subtask #3:

score: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #17:

score: 0
Wrong Answer
time: 913ms
memory: 160364kb

input:

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

output:

190330
676
6
462
36
5
180041
3
9236
4
7780
72
19848
100092
66812
28617
39645
66797
23
12
957
2542
7
68308
382
96
217
50
44
227
12909
1519
54616
1682
23
124101
45
12279
173381
10
33
21516
147537
59
40
5332
183402
67257
4281
7
172420
498
154897
113480
208
174
1
497
172594
1098
788
13628
39540
3716
748...

result:

wrong answer 5th numbers differ - expected: '40', found: '36'

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 1000ms
memory: 217080kb

input:

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

output:

83
102844
189133
4301
92257
199134
2955
92107
71
9820
154
58
585
199534
25
181468
415
197298
197137
6582
168359
192672
85
190398
76578
374
195122
170483
107444
246
199547
605
145
194309
1930
17315
106899
199374
1826
155739
166315
197339
13652
40209
58682
182853
102023
466
111
1636
181813
136479
1663...

result:

wrong answer 1st numbers differ - expected: '78', found: '83'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%