QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#253046 | #5313. Please Save Pigeland | KULIANLEN | WA | 0ms | 24108kb | C++14 | 2.8kb | 2023-11-16 17:02:50 | 2023-11-16 17:02:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 5e5 + 5,INF = 1e18;
#define ls (u << 1)
#define rs (u << 1 | 1)
#define sum(u) (tr[u].sum)
#define d(u) (tr[u].d)
#define tot(u) (tr[u].tot)
struct node{
int l,r;
int sum,d;
int tot;
}tr[N << 2];
int a[N],b[N];
void pushup(int u)
{
sum(u) = sum(ls) + sum(rs);tot(u) = tot(ls) + tot(rs);
d(u) = __gcd(d(ls), d(rs));
}
void build(int u,int l,int r)
{
if(l == r)tr[u] = {l, l, a[l], a[l], b[l]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
}
void upd(int u,int x,int d)
{
if(tr[u].l == tr[u].r)
{
sum(u) = x;
d(u) = x;tot(u) = x;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid)upd(ls, x, d);
else upd(rs, x, d);
pushup(u);
}
}
node que(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
return tr[u];
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
node res = {0,0,0,0};
if(l <= mid)
{
res = que(ls, l, r);
}
if(r > mid)
{
node tmp = que(rs ,l ,r);
res.sum += tmp.sum;
res.d = __gcd(res.d, tmp.d);
}
return res;
}
}
int quesum(int l,int r)
{
return que(1, l, r).sum;
}
int quegcd(int l,int r)
{
int sum = 0;
sum = que(1, 1, l).sum;
int d = 0;
if(l != r)
d = que(1, l + 1, r).d;
return abs(__gcd(sum, d));
}
bool st[N];vector<pair<int,int>> g[N];
int cnt,dfsn[N],rdfsn[N],n,k;
void dfs(int u,int f,int d)
{
dfsn[u] = INF;
if(st[u])dfsn[u] = ++cnt,rdfsn[u] = cnt,b[dfsn[u]] = d;
for(auto t : g[u])
{
int to = t.first,val = t.second;
if(to == f)continue;
dfs(to, u, d + val);
dfsn[u] = min(dfsn[u], dfsn[to]);
rdfsn[u] = max(rdfsn[to], rdfsn[u]);
}
}
void upd1(int l,int r,int x)
{
if(l < 1 || r > k || l > r)return;
upd(1, l, x);
if(r + 1 <= k)upd(1, r + 1, -x);
}
int ans = 1e18;
void dfs1(int u,int f)
{
int res = quegcd(1,k);
int dis = tr[1].tot;
ans = min(ans, dis / res);
for(auto t : g[u])
{
int to = t.first,val = t.second;
if(to == f)continue;
int l = dfsn[to],r = rdfsn[to];
if(l <= r)
{
upd1(l, r, -val);
upd1(1, l, val);
upd1(r + 1, k, val);
dfs1(to, u);
upd1(l, r, val);
upd1(1, l, -val);
upd1(r + 1, k, -val);
}
else
{
upd1(1, k, val);
dfs1(to, u);
upd1(1, k, -val);
}
}
}
signed main()
{
cin >> n >> k;
for(int i = 1;i <= k;i++)
{
int t;cin >> t;st[t] = true;
}
for(int i = 1;i < n;i++)
{
int u,v,w;cin >> u >> v >> w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dfs(1,0,0);
for(int i = 1;i <= k;i++)a[i] = b[i] - b[i - 1];
build(1,1,k);
dfs1(1,0);
cout << ans * 2 << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 24108kb
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: -100
Wrong Answer
time: 0ms
memory: 24096kb
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:
12
result:
wrong answer 1st numbers differ - expected: '24', found: '12'