QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#250303 | #5313. Please Save Pigeland | KULIANLEN | WA | 0ms | 47116kb | C++14 | 2.2kb | 2023-11-13 02:09:36 | 2023-11-13 02:09:37 |
Judging History
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'