QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#412391 | #6101. Ring Road | suomynonA | RE | 0ms | 18096kb | C++20 | 3.7kb | 2024-05-16 13:03:13 | 2024-05-16 13:03:13 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
const int N = 2e5;
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[N + 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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 15740kb
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: 15816kb
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: 0ms
memory: 18096kb
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...