QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#91428#5313. Please Save PigelandIndusRE 5ms32164kbC++142.3kb2023-03-28 21:26:122023-03-28 21:26:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-28 21:26:14]
  • 评测
  • 测评结果:RE
  • 用时:5ms
  • 内存:32164kb
  • [2023-03-28 21:26:12]
  • 提交

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], n, K, fa[N];
LL f[N], nf[N];
vector<pii> G[N];

struct GCD {
    int x, y, z;
    GCD(int _x = 0, int _y = 0, int _z = 0):x(_x), y(_y), z(_z){};
    GCD operator + (const int &w) const {
        if (!z) return GCD(0, 0, 0);
        return GCD(x + w, y, 1);
    }
    GCD operator + (const GCD &b) const {
        if (!z) return b;
        return GCD(x, __gcd(__gcd(y, b.y), b.x - x), z | b.z);
    }
}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), bz[u] += bz[k.fi];
        f[u] += f[k.fi] + (LL)bz[k.fi] * k.se, g[u] = g[u] + (g[k.fi] + k.se);
    }
}

void dfs2(int u) {
    vector<GCD> pre(G[u].size() + 1), suf(G[u].size() + 1);
    for(int i = 0; i < G[u].size(); ++i) {
        if (G[u][i].fi == fa[u]) pre[i + 1] = pre[i];
        else pre[i + 1] = pre[i] + (g[G[u][i].fi] + G[u][i].se);
    }
    for(int i = G[u].size() - 1; i >= 0; --i) {
        if (G[u][i].fi == fa[u]) suf[i] = suf[i + 1];
        else suf[i] = suf[i + 1] + (g[G[u][i].fi] + G[u][i].se);
    }
    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[i] + k.se) + (suf[i + 1] + k.se) + (up[u] + k.se);
        nf[k.fi] = nf[u] + (LL)(K - 2 * bz[k.fi]) * k.se, dfs2(k.fi);
    }
}

int main() {
    read(n), read(K);
    for(int i = 1; i <= K; i++) read(c[i]), bz[c[i]] = 1, g[c[i]].z = 1;
    if (n == 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], g[i].x = abs(g[i].x), g[i].y = abs(g[i].y);
        LL t = nf[i] / __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: 100
Accepted
time: 2ms
memory: 31472kb

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: 5ms
memory: 32164kb

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: 0
Accepted
time: 1ms
memory: 31192kb

input:

1 1
1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: -100
Runtime Error

input:

100000 1
79187
72704 72659 15
32741 43496 10
21580 97447 17
55758 36700 21
32116 3643 14
60460 58764 12
75894 50624 7
58295 49393 22
43733 17210 1
58093 68769 15
1086 58916 17
25632 37710 11
49555 92976 8
32547 27060 18
84896 12811 1
3196 1242 16
18870 78236 14
2414 7945 12
48745 15399 1
17648 83791...

output:


result: