QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#415393#6101. Ring RoadsuomynonARE 0ms0kbC++204.1kb2024-05-20 20:47:402024-05-20 20:47:40

Judging History

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

  • [2024-05-20 20:47:40]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: