QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#250303#5313. Please Save PigelandKULIANLENWA 0ms47116kbC++142.2kb2023-11-13 02:09:362023-11-13 02:09:37

Judging History

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

  • [2023-11-13 02:09:37]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:47116kb
  • [2023-11-13 02:09:36]
  • 提交

answer

#include <bits/stdc++.h>
#define eb emplace_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
using namespace std;

template<typename Tp>
void read(Tp &x) {
    x = 0; char ch = getchar(); int f = 0;
    for(; !isdigit(ch); f |= (ch == '-'), ch = getchar());
    for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
    if (f) x = ~x + 1;
}

typedef long long LL;
const int N = 5e5 + 5;
int c[N], bz[N], sbz[N], n, K, fa[N];
LL f[N], nf[N];
vector<pii> G[N];

struct GCD {
    LL x, y; int z;
    GCD(LL _x = 0, LL _y = 0, int _z = 0):x(_x), y(_y), z(_z){};
    GCD operator + (const int &w) const {return GCD(x + w, y, z);}
    GCD operator + (const GCD &b) const {
        if (!z) return b;
        if (!b.z) return *this;
        return GCD(x, __gcd(__gcd(y, b.y), b.x ), 1);
    }
}g[N], up[N];

void dfs1(int u) {
    for(pii k : G[u]) if (k.fi ^ fa[u]) {
        fa[k.fi] = u, dfs1(k.fi), sbz[u] += sbz[k.fi];
        f[u] += f[k.fi] + (LL)sbz[k.fi] * k.se, g[u] = g[u] + (g[k.fi] + k.se);
    }
}

void dfs2(int u) {
    GCD pre;
    for(int i = 0; i < G[u].size(); ++i) if (G[u][i].fi ^ fa[u]) {
        pii k = G[u][i]; up[k.fi] = pre, pre = pre + (g[k.fi] + k.se);
    }
    reverse(G[u].begin(), G[u].end()), pre = GCD();
    for(int i = 0; i < G[u].size(); ++i) if (G[u][i].fi ^ fa[u]) {
        pii k = G[u][i]; up[k.fi] = up[k.fi] + pre, pre = pre + (g[k.fi] + k.se);
    }
    pre = GCD(0, 0, bz[u] > 0) + up[u];
    for(int i = 0; i < G[u].size(); ++i) if (G[u][i].fi ^ fa[u]) {
        pii k = G[u][i]; up[k.fi] = (up[k.fi] + pre) + k.se;
        nf[k.fi] = nf[u] + (LL)(K - 2 * sbz[k.fi]) * k.se, dfs2(k.fi);
    }
}

int main() {
    read(n), read(K);
    for(int i = 1; i <= K; i++) read(c[i]), sbz[c[i]] = bz[c[i]] = g[c[i]].z = 1;
    if (K == 1) return puts("0"), 0;
    for(int i = 1, u, v, w; i < n; i++)
        read(u), read(v), read(w), G[u].eb(mp(v, w)), G[v].eb(mp(u, w));
    dfs1(1), nf[1] = f[1], dfs2(1);
    LL ans = -1;
    for(int i = 1; i <= n; i++) {
        g[i] = g[i] + up[i];
        LL t = nf[i] / abs(__gcd(g[i].x, g[i].y));
        if (ans == -1 || t < ans) ans = t;
    }
    printf("%lld\n", 2LL * ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 47116kb

input:

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

output:

14

result:

wrong answer 1st numbers differ - expected: '8', found: '14'