QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#415386#6101. Ring RoadsuomynonAML 317ms58304kbC++204.0kb2024-05-20 20:43:282024-05-20 20:43:28

Judging History

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

  • [2024-05-20 20:43:28]
  • 评测
  • 测评结果:ML
  • 用时:317ms
  • 内存:58304kb
  • [2024-05-20 20:43:28]
  • 提交

answer

#include <bits/stdc++.h>
using i64 = long long;
const int N = 2e5, Q = 2.5e5;
const i64 Inf = 1e18;
int n;
struct Edge { int x, y; i64 z; }ed[N * 2 + 5];
int tot;
namespace Init {

int n;
std::vector<std::pair<int, i64>> v[N + 5];
void dfs(int x) {
    for (int i = 0, pre = x; i < (int)v[x].size(); ++i) if (v[x][i].first > x) {
        ++::n;
        ed[++tot] = {pre, ::n, 0}, ed[++tot] = {::n, v[x][i].first, v[x][i].second};
        pre = ::n;
    }
    for (auto [i, c] : v[x]) if (i > x) dfs(i);
}
void solve() {
    std::cin >> n;
    for (int i = 2, x; i <= n; ++i) {
        i64 y;
        std::cin >> x >> y;
        v[x].push_back({i, y}), v[i].push_back({x, y});
    }
    ::n = n, dfs(1);
}

}
std::vector<std::array<int, 2>> tr[N + 5], gr[N + 5];
int q;
i64 ans[Q + 5];
int siz[N + 5], rt, mxs;
bool vis[N + 5];
void getrt(int x, int fa, int tot) {
    siz[x] = 1;
    for (auto [i, c] : tr[x]) if (!vis[c] and c != fa) getrt(i, c, tot), siz[x] += siz[i];
    if (std::max(siz[x], tot - siz[x]) < mxs) rt = fa, mxs = std::max(siz[x], tot - siz[x]);
}
std::vector<int> nd;
namespace Dijkstra {

std::priority_queue<std::pair<i64, int>> hp;
void solve(int s, i64 *dis) {
    for (auto i : nd) dis[i] = Inf;
    dis[s] = 0, hp.push({0, s});
    while (hp.size()) {
        auto [d, p] = hp.top();
        d = -d, hp.pop();
        if (d > dis[p]) continue;
        for (auto [i, c] : gr[p]) if (d + ed[c].z < dis[i])
            dis[i] = d + ed[c].z, hp.push({-dis[i], i});
    }
}

}
int col[N + 5];
void add(int x, int fa, int v) {
    nd.push_back(x), col[x] = v;
    for (auto [i, c] : tr[x]) if (!vis[c] and c != fa) add(i, c, v);
}
i64 dis[6][N + 5];
std::array<int, 3> qry[Q + 5], tmp[Q + 5];
void solve(int p, int l, int r) {
    add(ed[p].x, p, 1), add(ed[p].y, p, 2);
    std::vector<int> br;
    for (auto i : nd) for (auto [j, c] : gr[i])
        if (col[i] == 1 and col[j] == 2) br.push_back(i), br.push_back(j);
    for (int i = 0; i < (int)br.size(); ++i) Dijkstra::solve(br[i], dis[i]);
    for (int p = l; p <= r; ++p) {
        auto [x, y, c] = qry[p];
        for (int i = 0; i < (int)br.size(); ++i)
            for (int j = 0; j < (int)br.size(); ++j)
                ans[c] = std::min(ans[c], dis[i][x] + dis[i][br[j]] + dis[j][y]);
    }
    int cnt = 0;
    for (int p = l; p <= r; ++p) {
        auto [x, y, c] = qry[p];
        if ((col[x] & 1) and (col[y] & 1)) ++cnt;
    }
    int c1 = l, c0 = l + cnt;
    for (int p = l; p <= r; ++p) {
        auto [x, y, c] = qry[p];
        if (col[x] == col[y]) {
            if (col[x] & 1) tmp[c1++] = qry[p];
            else tmp[c0++] = qry[p];
        }
    }
    for (int i = l; i <= r; ++i) qry[i] = tmp[i];
    for (auto i : nd) {
        col[i] = 0;
        for (int j = 0; j < (int)br.size(); ++j) dis[j][i] = 0;
    }
    nd.clear(), vis[p] = 1;
    getrt(ed[p].x, 0, n);
    if (l < c1) rt = 0, mxs = n, getrt(ed[p].x, 0, siz[ed[p].x]), solve(rt, l, c1 - 1);
    if (c1 < c0) rt = 0, mxs = n, getrt(ed[p].y, 0, siz[ed[p].y]), solve(rt, c1, c0 - 1);
}
int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    Init::solve();
    for (int i = 1; i < n; ++i) {
        tr[ed[i].x].push_back({ed[i].y, i});
        gr[ed[i].x].push_back({ed[i].y, i});
        gr[ed[i].y].push_back({ed[i].x, i});
        tr[ed[i].y].push_back({ed[i].x, i});
    }
    int pre = 0;
    i64 x = 0;
    for (int i = 2; i <= n; ++i) if ((int)tr[i].size() == 1) {
        if (pre) ed[++tot] = {pre, i, x}, gr[pre].push_back({i, tot}), gr[i].push_back({pre, tot});
        std::cin >> x, pre = i;
    }
    for (int i = 2; i <= n; ++i) if ((int)tr[i].size() == 1) {
        ed[++tot] = {pre, i, x}, gr[pre].push_back({i, tot}), gr[i].push_back({pre, tot});
        break;
    }
    std::cin >> q;
    for (int i = 1; i <= q; ++i) std::cin >> qry[i][0] >> qry[i][1], qry[i][2] = i, ans[i] = Inf;
    rt = 0, mxs = n, getrt(1, 0, n), solve(rt, 1, q);
    for (int i = 1; i <= q; ++i) std::cout << ans[i] << "\n";
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 22312kb

input:

4
1 9
1 8
1 0
9 9 9
6
1 2
1 3
1 4
2 3
2 4
3 4

output:

9
8
0
9
9
8

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 22084kb

input:

11
1 9
1 8
3 0
4 7
4 1
3 6
1 0
8 7
8 1
10 6
0 0 0 0 0 0
21
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
7 1
8 2
9 3
10 4
11 5
1 6
2 7
3 8
4 9
5 10
6 11

output:

7
8
8
7
7
7
0
7
1
7
7
7
1
7
0
7
0
8
1
6
0

result:

ok 21 numbers

Test #3:

score: 0
Accepted
time: 4ms
memory: 22056kb

input:

11
1 9
1 8
3 0
4 7
4 1
3 6
1 0
8 7
8 1
10 6
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000
21
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
7 1
8 2
9 3
10 4
11 5
1 6
2 7
3 8
4 9
5 10
6 11

output:

9
8
8
15
9
14
0
7
1
7
14
9
15
9
22
9
23
8
15
16
16

result:

ok 21 numbers

Test #4:

score: 0
Accepted
time: 202ms
memory: 55800kb

input:

99998
1 683940
1 335116
3 198362
4 28825
5 625394
6 314200
7 270653
8 61629
9 650997
10 693039
11 159577
12 466708
13 715788
14 262771
15 615302
16 1457
17 650381
18 542652
19 101993
20 197937
21 474452
22 859631
23 327526
24 705522
25 500710
26 595050
27 577264
28 955258
29 269967
30 4012
31 471435...

output:

683940
335116
533478
562303
1187697
1501897
1772550
1834179
2485176
3178215
3337792
3804500
4520288
4783059
5398361
5399818
6050199
6592851
6694844
6892781
7367233
8226864
8554390
9259912
9760622
10355672
10932936
11888194
12158161
12162173
12633608
13385421
13746582
14637654
14649654
15558759
15771...

result:

ok 250000 numbers

Test #5:

score: 0
Accepted
time: 317ms
memory: 56164kb

input:

99998
1 479670338308
2 121499701200
3 858712975908
4 144714509693
5 285977224040
6 864876191776
7 68574926716
8 310308615852
9 502806496434
10 361482163495
11 765497528076
12 895859015474
13 334706003457
14 379981526252
15 36757813515
16 157157422672
17 349512227463
18 338990361716
19 163391039440
2...

output:

479670338308
601170039508
1459883015416
1604597525109
1890574749149
2755450940925
2824025867641
3134334483493
3637140979927
3998623143422
4764120671498
5659979686972
5994685690429
6374667216681
6411425030196
6568582452868
6918094680331
7257085042047
7420476081487
7622906189099
8454399662437
89043817...

result:

ok 250000 numbers

Test #6:

score: 0
Accepted
time: 281ms
memory: 58304kb

input:

99998
1 178045123943
2 547685852175
3 121241296998
4 254770970696
5 492051406869
6 202334193904
7 510144241379
8 319988611700
9 116337235366
10 879642794656
11 685411730399
12 350924727333
13 594085342571
14 548936135915
15 208962464142
16 862456709774
17 288075015418
18 829298359525
19 618337059019...

output:

178045123943
725730976118
846972273116
1101743243812
1593794650681
1796128844585
2306273085964
2626261697664
2742598933030
3622241727686
4307653458085
4658578185418
5252663527989
5801599663904
6010562128046
6873018837820
7161093853238
7990392212763
8608729271782
9144448114015
9555400007353
973058283...

result:

ok 250000 numbers

Test #7:

score: -100
Memory Limit Exceeded

input:

99998
1 505218
1 389104
3 722814
4 114842
5 630847
6 266652
7 69086
8 188782
9 302082
10 791859
11 868547
12 207649
13 144886
14 249343
15 348080
16 430422
17 677611
18 246267
19 45035
20 530145
21 674630
22 619198
23 586278
24 546781
25 135381
26 191829
27 974891
28 296123
29 309858
30 867733
31 57...

output:


result: