QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#69450 | #5313. Please Save Pigeland | magicduck# | RE | 9ms | 32540kb | C++14 | 3.0kb | 2022-12-27 17:05:57 | 2022-12-27 17:05:59 |
Judging History
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;
}
详细
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