QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#415386 | #6101. Ring Road | suomynonA | ML | 317ms | 58304kb | C++20 | 4.0kb | 2024-05-20 20:43:28 | 2024-05-20 20:43:28 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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...