QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#415393 | #6101. Ring Road | suomynonA | RE | 0ms | 0kb | C++20 | 4.1kb | 2024-05-20 20:47:40 | 2024-05-20 20:47:40 |
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];
std::vector<int> br;
void solve(int p, int l, int r, int count = 0) {
assert(count > 30);
add(ed[p].x, p, 1), add(ed[p].y, p, 2);
br.clear();
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, count + 1);
if (c1 < c0) rt = 0, mxs = n, getrt(ed[p].y, 0, siz[ed[p].y]), solve(rt, c1, c0 - 1, count + 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: 0
Runtime Error
input:
4 1 9 1 8 1 0 9 9 9 6 1 2 1 3 1 4 2 3 2 4 3 4