QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91427 | #5313. Please Save Pigeland | Indus | RE | 4ms | 32320kb | C++14 | 2.3kb | 2023-03-28 21:24:05 | 2023-03-28 21:24:06 |
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], 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;
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);
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 32320kb
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: 2ms
memory: 31144kb
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