QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#252722#5313. Please Save PigelandricofxRE 3ms34436kbC++203.4kb2023-11-16 08:49:132023-11-16 08:49:13

Judging History

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

  • [2023-11-16 08:49:13]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:34436kb
  • [2023-11-16 08:49:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 998244353;
const int N = 5e5 + 5;
const int inf = 0x3f3f3f3f;

int dfc;
int n, k, c[N], rc[N], dfn[N], rnk[N], fr[N], gr[N], dep[N], b[N], id[N], siz[N];
vector<pair<int, int>> G[N];

void dfs(int u, int fa) {
	dfn[u] = ++dfc;
	rnk[dfc] = u;
	siz[u] = 1;
	for (auto [v, w] : G[u]) if (v != fa) {
		dep[v] = dep[u] + w;
		dfs(v, u);
		siz[u] += siz[v];
	}
}
int tr[N];
void add(int x, int v) {
	for (; x <= k; x += x & -x) tr[x] += v;
}
int qry(int x) {
	int res = 0;
	for (; x; x -= x & -x) res += tr[x];
	return res;
}
void add(int l, int r, int v) {
	add(l, v), add(r + 1, -v);
}
#define lson (p << 1)
#define rson ((p << 1) | 1) 
#define mid ((l + r) >> 1)
int gc[N];
void build(int p, int l, int r) {
	if (l == r) {
		gc[p] = b[l];
		return;
	}
	build(lson, l, mid), build(rson, mid + 1, r);
	gc[p] = gcd(gc[lson], gc[rson]);
}
void modify(int p, int l, int r, int pos, int det) {
	if (l == r) {
		gc[p] += det;
		return;
	}
	if (pos <= mid) modify(lson, l, mid, pos, det);
	else modify(rson, mid + 1, r, pos, det);
	gc[p] = gcd(gc[lson], gc[rson]);
}
int query(int p, int l, int r, int L, int R) {
	if (l > R || r < L) return 0;
	if (l >= L && r <= R) return gc[p];
	return gcd(query(lson, l, mid, L, R), query(rson, mid + 1, r, L, R));
}
int get(int l = 1, int r = k) {
	return gcd(qry(l), l == r ? 0 : query(1, 1, k, l + 1, r)); 
}
void modify(int l, int r, int v) {
	if (l > r) return;
	modify(1, 1, k, l, v);
	if (l != k) modify(1, 1, k, l + 1, -v);
	if (r != k) modify(1, 1, k, r, -v);
	if (r + 1 <= k) modify(1, 1, k, r + 1, v);
}
ll ans, sum;
void dfs1(int u, int fa) {
	ans = min(ans, sum / get(1, k));
	//cout << u << ' ' << sum  << ' ' << get() << '\n';
	for (auto [v, w] : G[u]) if (v != fa) {
		int l = gr[dfn[v]], r = fr[dfn[v] + siz[v] - 1];
		// cout << "* "  << v  << ' '<< l << ' ' << r << '\n';
		l = max(l, 1);
		if (l <= r) {
			add(l, r, -w);
			if (l != 1) add(1, l - 1, w);
			if (r != k) add(r + 1, k, w);
			modify(l, r, -w);
			modify(1, l - 1, w);
			modify(r + 1, k, w);
			sum += (k - 2ll * (r - l + 1)) * w;
		} else {
			sum += k * w;
			add(l, r, w);
			modify(1, k, w);
		}
		dfs1(v, u);
		if (l <= r) {
			add(l, r, w);
			if (l != 1) add(1, l - 1, -w);
			if (r != k) add(r + 1, k, -w);
			modify(l, r, w);
			modify(1, l - 1, -w);
			modify(r + 1, k, -w);
			sum -= (k - 2ll * (r - l + 1)) * w;
		} else {
			sum -= k * w;
			add(l, r, -w);
			modify(1, k, -w);
		}
	}
}

void solve() {
	cin >> n >> k;
	for (int i = 1; i <= k; i++) {
		cin >> c[i];
		rc[c[i]] = 1;
	}
	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, 1);
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (rc[rnk[i]]) fr[i] = ++cnt, id[cnt] = rnk[i];
		else fr[i] = fr[i - 1];
	}
	cnt = k + 1;
	gr[n + 1] = inf;
	for (int i = n; i; i--) {
		if (rc[rnk[i]]) gr[i] = --cnt;
		else gr[i] = gr[i + 1];
	}
	cnt = 0;
	for (int i = 1; i <= k; i++) b[i] = dep[id[i]] - dep[id[i - 1]];
	for (int i = 1; i <= k; i++) add(i, b[i]), sum += dep[id[i]];
	build(1, 1, k);
	ans = 1e18;
	dfs1(1, 1);
	cout << ans * 2 << '\n';
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T = 1;
	//cin >> T;
	while (T--) solve();
	return 0;
}

详细

Test #1:

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

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: 3ms
memory: 34436kb

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

output:


result: