QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#253070#5313. Please Save PigelandKULIANLENWA 58ms29992kbC++143.3kb2023-11-16 17:17:152023-11-16 17:17:16

Judging History

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

  • [2023-11-16 17:17:16]
  • 评测
  • 测评结果:WA
  • 用时:58ms
  • 内存:29992kb
  • [2023-11-16 17:17:15]
  • 提交

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)
#define mk(u) (tr[u].mk)
struct node{
	int l,r;
	int sum,d;
	int tot,mk;
}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 pushdown(int u)
{
	tot(ls) += mk(u) * (tr[ls].r - tr[ls].l + 1);
	tot(rs) += mk(u) * (tr[rs].r - tr[rs].l + 1);
	mk(ls) += mk(u);mk(rs) += mk(u);
	mk(u) = 0;
}

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 upd2(int u,int l,int r,int d)
{
	if(tr[u].l >= l && tr[u].r <= r)
	{
		tot(u) += d * (tr[u].r - tr[u].l + 1);
		mk(u) += d;
	}
	else 
	{
		pushdown(u);
		int mid = tr[u].l + tr[u].r >> 1;
		if(l <= mid)upd2(ls, l, r, d);
		if(r > mid)upd2(rs, l, r, d);
		pushup(u);
	}
}
void upd(int u,int x,int d)
{
	if(tr[u].l == tr[u].r)
	{
		sum(u) = x;
		d(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,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);
			res.tot += tmp.tot;
		}
		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);
	upd2(1, l, r, x);
	if(r + 1 <= k)upd(1, r + 1, -x),upd2(1, r + 1, k, -x);	
}

int ans = 1e18;
void dfs1(int u,int f)
{
	int res = quegcd(1,k);
	int dis = tr[1].tot;
	// cout << res <<" " << dis << endl;
	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);
	if(n!=1)
	dfs1(1,0);
	else ans = 0;
	cout << ans * 2 << endl;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 24048kb

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: 0ms
memory: 24084kb

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: 4ms
memory: 24044kb

input:

1 1
1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: -100
Wrong Answer
time: 58ms
memory: 29992kb

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:

2

result:

wrong answer 1st numbers differ - expected: '0', found: '2'