QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#718778#5313. Please Save Pigelandlllei#WA 1ms3624kbC++207.7kb2024-11-06 21:25:212024-11-06 21:25:25

Judging History

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

  • [2024-11-06 21:25:25]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3624kb
  • [2024-11-06 21:25:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

constexpr LL INF = 1e18;

template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = init_[l];
                return;
            }
            int mid = (l + r) / 2;
            build(2 * p, l, mid);
            build(2 * p + 1, mid + 1, r);
            pull(p);
        };
        build(1, 0, n - 1);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    template<class F>
    void modify(int p, int l, int r, int x, F op) {
        if (l == r) {
            op(info[p]);
            return;
        }
        int mid = (l + r) >> 1;
        push(p);
        if (x <= mid) {
            modify(2 * p, l, mid, x, op);
        } else {
            modify(2 * p + 1, mid + 1, r, x, op);
        }
        pull(p);
    }
    template<class F>
    void modify(int p, const F op) {
        modify(1, 0, n - 1, p, op);
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int mid = (l + r) / 2;
        push(p);
        if (x <= mid) {
            modify(2 * p, l, mid, x, v);
        } else {
            modify(2 * p + 1, mid + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n - 1, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int mid = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, mid, x, y) + rangeQuery(2 * p + 1, mid + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n - 1, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int mid = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, mid, x, y, v);
        rangeApply(2 * p + 1, mid + 1, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n - 1, l, r, v);
    }
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F pred, Info &pre) {
        if (l > y || r < x) {
            return -1;
        }

        if (l >= x && r <= y) {
            if (!pred(pre + info[p])) {
                pre = pre + info[p];
                return -1;
            }
        }

        if (l == r) {
            return l;
        }

        int mid = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, mid, x, y, pred, pre);
        if (res == -1) {
            res = findFirst(2 * p + 1, mid + 1, r, x, y, pred, pre);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F pred) {
        Info pre;
        return findFirst(1, 0, n - 1, l, r, pred, pre);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F pred, Info &suf) {
        if (l > y || r < x) {
            return -1;
        }
        if (l >= x && r <= y) {
            if (!pred(info[p] + suf)) {
                suf = info[p] + suf;
                return -1;
            }
        }
        if (l == r) {
            return l;
        }
        int mid = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, mid + 1, r, x, y, pred, suf);
        if (res == -1) {
            res = findLast(2 * p, l, mid, x, y, pred, suf);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F pred) {
        Info suf;
        return findLast(1, 0, n - 1, l, r, pred, suf);
    }
};
 
struct Tag {
    LL add = 0;
    void apply(Tag t) & {
        add += t.add;
    }
};
 
struct Info {
    int len;
    LL g, sum;
    Info(int len = 0, LL g = 0, LL sum = 0) : len(len), g(g), sum(sum) {}

    void apply(Tag t) & {
        sum += len * t.add;
    }
};
 
Info operator+(const Info &a, const Info &b) {
    return Info(a.len + b.len, gcd(a.g, b.g), a.sum + b.sum);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(k);
    vector<bool> vis(n);
    vector<int> id(n, -1), rid(n, -1);
    int cnt = 0;
    for (int i = 0; i < k; ++i) {
        cin >> a[i];
        --a[i];
    }
    vector<int> L(n, n), R(n, -1);

    vector<vector<array<int, 2>>> e(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }

    vector<int> dis(n);
    auto dfs = [&](auto &&self, int u, int fa) -> void {
        id[u] = cnt;
        rid[cnt] = u;
        cnt++;
        if (vis[u]) {
            L[u] = R[u] = id[u];
        }
        for (auto [v, w] : e[u]) {
            if (v == fa) {
                continue;
            }
            dis[v] = dis[u] + w;
            self(self, v, u);
            L[u] = min(L[u], L[v]);
            R[u] = max(R[u], R[v]);
        }
    };
    dfs(dfs, 0, -1);

    vector<Info> init(k);
    sort(a.begin(), a.end(), [&](const auto &x, const auto &y) {
        return id[x] < id[y];
    });
    for (int i = 0; i < k; ++i) {
        init[i] = Info(1, i == 0 ? dis[a[i]] : dis[a[i]] - dis[a[i - 1]], dis[a[i]]);
    }

    LazySegmentTree<Info, Tag> seg(init);

    LL ans = INF;

    auto myMod = [&](int l, int r, LL w) {
        if (l > r) {
            return;
        }
        seg.rangeApply(l, r, {w});
        if (r + 1 < k) {
            auto op = [&](Info &info) {
                info.g -= w;
            };
            seg.modify(r + 1, op);
        }
        auto op = [&](Info &info) {
            info.g += w;
        };
        seg.modify(l, op);
    };

    auto dfs1 = [&](auto &&self, int u, int fa) -> void {
        Info info = seg.info[1];
        ans = min(ans, info.sum / info.g * 2);
        for (auto [v, w] : e[u]) {
            if (v == fa) {
                continue;
            }
            if (L[v] <= R[v]) {
                myMod(L[v], R[v], -w);
                myMod(R[v] + 1, k - 1, w);
                myMod(0, L[v] - 1, w);
            } else {
                myMod(0, k - 1, w);
            }
            self(self, v, u); 
            if (L[v] <= R[v]) {
                myMod(L[v], R[v], w);
                myMod(R[v] + 1, k - 1, -w);
                myMod(0, L[v] - 1, -w);
            } else {
                myMod(0, k - 1, -w);
            }
        }
    };
    dfs1(dfs1, 0, -1);

    cout << ans << '\n';
    return 0;
}

/*
5 3
3 4 5
1 2 2
2 3 4
2 5 4
3 4 6
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3528kb

input:

5 3
3 4 5
1 2 2
2 3 4
2 5 4
3 4 6

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3624kb

input:

10 3
1 7 10
7 6 3
1 8 3
3 6 3
8 6 2
4 1 1
10 6 4
2 8 3
9 10 3
5 10 3

output:

34

result:

wrong answer 1st numbers differ - expected: '24', found: '34'