QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69450#5313. Please Save Pigelandmagicduck#RE 9ms32540kbC++143.0kb2022-12-27 17:05:572022-12-27 17:05:59

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-27 17:05:59]
  • 评测
  • 测评结果:RE
  • 用时:9ms
  • 内存:32540kb
  • [2022-12-27 17:05:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T> inline void read(T &F) {
    int R = 1; F = 0; char CH = getchar();
    for(; !isdigit(CH); CH = getchar()) if(CH == '-') R = -1;
    for(; isdigit(CH); CH = getchar()) F = F * 10 + CH - 48;
    F *= R;
}
inline void file(string str) {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 5e5 + 10;
LL gcd(LL x, LL y) {
    return y ? gcd(y, x % y) : x;
}
vector<pair<int, int> > edge[N]; int n, flag[N], k;
struct node {
    int cnt; LL dis, s, g;
    friend node operator + (const node &a, const node &b) {
        if(a.cnt == 0) return b; else if(b.cnt == 0) return a;

        node c; c.g = gcd(gcd(a.g, b.g), abs(a.s - b.s));
        c.s = a.s; c.dis = a.dis + b.dis; c.cnt = a.cnt + b.cnt;
        return c;
    }
    void clr() {
        cnt = dis = s = g = 0;
    }
    void init(int x) {
        cnt++; dis += x;
        if(cnt == 1) {
            s = x, g = 0; return;
        }
        g = gcd(g, abs(x - s)); s = x;
    }
    node() : cnt(0), dis(0), s(0), g(0) {}
}f[N];
void dfs(int x, int fa) {
    if(flag[x]) f[x].init(0);
    for(auto i : edge[x]) {
        if(i.first == fa) continue;
        dfs(i.first, x); node p = f[i.first];
        p.dis += 1LL * p.cnt * i.second; p.s += i.second;
        f[x] = f[x] + p;
    }
}
LL ans;
void solve(int x, int fa, node T) {
    node G = f[x] + T;
    ans = min(ans, G.dis / gcd(G.g, G.s));
    const int len = edge[x].size();
    vector<node> pre(len), succ(len);
    node l;
    for(int i = 0; i < len; i++) {
        if(edge[x][i].first == fa) {
            pre[i] = l; continue;
        }
        node p = f[edge[x][i].first];
        p.dis += 1LL * p.cnt * edge[x][i].second;
        p.s += edge[x][i].second;
        pre[i] = (l + p), l = pre[i];
    }
    l.clr();
    for(int i = len - 1; i >= 0; i--) {
        if(edge[x][i].first == fa) {
            succ[i] = l; continue;
        }
        node p = f[edge[x][i].first];
        p.dis += 1LL * p.cnt * edge[x][i].second;
        p.s += edge[x][i].second;
        succ[i] = (l + p), l = succ[i];
    }
    for(int i = 0; i < len; i++) {
        if(edge[x][i].first == fa) continue;
        node P = T;
        if(i) P = P + pre[i - 1];
        if(i + 1 < len) P = P + succ[i + 1];
        if(flag[x]) P.init(0);
        P.dis += 1LL * P.cnt * edge[x][i].second;
        P.s += edge[x][i].second;
        solve(edge[x][i].first, x, P);
    }
}
int main() {
    //file("");
    read(n), read(k);
    for(int i = 1; i <= k; i++) {
        int x; read(x);
        flag[x] = 1;
    }
    for(int i = 1; i < n; i++) {
        int x, y, z; read(x), read(y), read(z);
        edge[x].emplace_back(y, z);
        edge[y].emplace_back(x, z);
    }
    ans = 1e18; dfs(1, 0);
    node T; solve(1, 0, T);
    cout << ans * 2 << '\n';
    #ifdef _MagicDuck
        fprintf(stderr, "# Time: %.3lf s", (double)clock() / CLOCKS_PER_SEC);
    #endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 32416kb

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: 0
Accepted
time: 9ms
memory: 32540kb

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:

24

result:

ok 1 number(s): "24"

Test #3:

score: -100
Runtime Error

input:

1 1
1

output:


result: