QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412396 | #6101. Ring Road | suomynonA | RE | 3ms | 16044kb | C++20 | 3.7kb | 2024-05-16 13:11:05 | 2024-05-16 13:11:07 |
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 + 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];
void solve(int p, std::vector<std::array<int, 3>> qry) {
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 (auto [x, y, c] : qry)
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]);
std::vector<std::array<int, 3>> qr[2];
for (auto [x, y, c] : qry) if (col[x] == col[y]) qr[col[x] & 1].push_back({x, y, c});
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 (qr[1].size()) rt = 0, mxs = n, getrt(ed[p].x, 0, siz[ed[p].x]), solve(rt, qr[1]);
if (qr[0].size()) rt = 0, mxs = n, getrt(ed[p].y, 0, siz[ed[p].y]), solve(rt, qr[0]);
}
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;
std::vector<std::array<int, 3>> qry;
for (int i = 1, x, y; i <= q; ++i) std::cin >> x >> y, qry.push_back({x, y, i}), ans[i] = Inf;
rt = 0, mxs = n, getrt(1, 0, n), solve(rt, qry);
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: 15860kb
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: 15748kb
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: 3ms
memory: 16044kb
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: -100
Runtime Error
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...