Logo Wy Online Judge

WyOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#420#54. 「NOIP2012」疫情控制Pigsyy10018132ms103024kbC++232.9kb2025-04-24 11:32:472025-04-24 11:42:53

answer

#include <bits/stdc++.h>
#pragma GCC("O3, Ofast, unroll-loop")
#define fi first
#define se second
using namespace std;
using i64 = long long;
using pii = pair<int, i64>;

const int maxn = 300005;

int n, m;
int h[maxn], e[maxn * 2], ne[maxn * 2], w[maxn * 2], idx;
int army[maxn], fa[maxn][20], tsp;
i64 dist[maxn][20];
int vis[maxn], dp[maxn];
int dfn[maxn], ord[maxn], sz[maxn];
std::vector<i64> rest[maxn];

void add(int a, int b, int c) {
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

void dfs1(int u) {
	for (int j = 1; j <= __lg(n); j ++) {
		dist[u][j] = dist[u][j - 1] + dist[fa[u][j - 1]][j - 1];
		fa[u][j] = fa[fa[u][j - 1]][j - 1];
	}
	ord[dfn[u] = ++ tsp] = u, sz[u] = 1;
	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		if (v == fa[u][0]) continue;
		dist[v][0] = w[i], fa[v][0] = u;
		dfs1(v);
		sz[u] += sz[v];
	}
}


int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;

	memset(h, -1, sizeof h);
	for (int i = 1; i < n; i ++) {
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
	}
	
	cin >> m;
	for (int i = 1; i <= m; i ++)
		cin >> army[i];

	dfs1(1);

	i64 lo = 0, ro = 3e15;
	while (lo <= ro) {
		i64 mid = lo + ro >> 1;

		memset(vis, 0, sizeof vis);
		for (int i = h[1]; ~i; i = ne[i])
			rest[e[i]].clear();

		for (int i = 1; i <= m; i ++) {
			int u = army[i];
			i64 tot = mid;
			for (int j = __lg(n); j >= 0; j -- )
				if (fa[u][j] > 1 && dist[u][j] <= tot)
					tot -= dist[u][j], u = fa[u][j];
			vis[u] = 1;
			if (fa[u][0] == 1) rest[u].push_back(tot);
		}

		memset(dp, 0, sizeof dp);
		std::multiset<pair<i64, int>> usable;
		for (int i = h[1]; ~i; i = ne[i]) {
			int rt = e[i];
			for (int j = dfn[rt] + sz[rt] - 1; j >= dfn[rt]; j --) {
				int u = ord[j];
				if (u != rt) dp[u] = vis[u];
				bool temp = 1, leaf = 1;
				for (int k = h[u]; ~k; k = ne[k]) {
					int v = e[k];
					if (v == fa[u][0]) continue;
					leaf = 0, temp &= dp[v];
				}
				if (!leaf) dp[u] |= temp;
			}

			sort(rest[rt].begin(), rest[rt].end());
			for (auto t : rest[rt])
				usable.insert({t - w[i], rt});
		}

		bool ok = 1;
		for (int i = h[1]; ~i; i = ne[i]) {
			int u = e[i];
			if (!dp[u]) {
				auto it = usable.lower_bound({w[i], 0});
				i64 val = 1e18;
				for (auto t : rest[u])
					if (usable.find({t - w[i], u}) != usable.end()) {
						val = t - w[i];
						break;
					}
				if (it == usable.end() && val == 1e18) {
					ok = false;
					break;
				}
				if (it == usable.end() || val < (*it).fi)
					usable.erase(usable.find({val, u}));
				else usable.erase(it);
			}
		}

		if (ok) ro = mid - 1;
		else lo = mid + 1;
	}

	if (ro == 3e15) cout << -1 << endl;
	else cout << ro + 1 << endl;

	return 0;
}
/*
7
1 2 193156
1 3 543535
2 4 458552
4 5 777976
3 6 475533
1 7 876969
3
7 4 7 
*/

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 17ms
memory: 14756kb

input:

10
2 1 3
2 3 4
1 4 7
5 1 9
6 1 2
4 7 9
7 8 8
9 8 8
1 10 2
5
2 8 5 4 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 5
Accepted
time: 12ms
memory: 14728kb

input:

5
1 2 1
2 3 1
1 4 1
1 5 1
3
2 3 3

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: 5
Accepted
time: 13ms
memory: 14992kb

input:

50
1 2 7528
3 2 3807
3 4 4184
5 2 5932
5 6 6827
7 4 392
8 5 5041
7 9 2394
6 10 999
1 11 4033
12 9 63...

output:

27815

result:

ok 1 number(s): "27815"

Test #4:

score: 5
Accepted
time: 14ms
memory: 16428kb

input:

50
2 1 284
3 1 2512
4 2 7246
5 4 6989
5 6 5151
7 5 6614
8 2 4101
5 9 4137
10 2 885
11 1 1754
12 6 29...

output:

31271

result:

ok 1 number(s): "31271"

Test #5:

score: 5
Accepted
time: 14ms
memory: 16428kb

input:

500
1 2 24167
3 1 1774
4 2 4769
5 1 11790
5 6 19265
1 7 26115
3 8 3207
4 9 15064
8 10 16988
1 11 550...

output:

140558

result:

ok 1 number(s): "140558"

Test #6:

score: 5
Accepted
time: 16ms
memory: 16544kb

input:

1000
1 2 14265
3 1 16938
1 4 18039
5 2 16371
6 3 721
4 7 9026
5 8 10772
5 9 23686
10 4 4853
6 11 283...

output:

129901

result:

ok 1 number(s): "129901"

Test #7:

score: 5
Accepted
time: 40ms
memory: 23708kb

input:

10000
1 2 3954
2 3 8270
4 2 4154
5 4 22890
2 6 8361
7 1 16216
8 2 29099
9 8 13270
5 10 12790
7 11 30...

output:

80321

result:

ok 1 number(s): "80321"

Test #8:

score: 5
Accepted
time: 56ms
memory: 23820kb

input:

10000
2 1 15489
2 3 5426
4 2 25769
5 1 24696
6 2 736
1 7 17986
8 4 5614
9 6 5957
2 10 1705
10 11 145...

output:

30887

result:

ok 1 number(s): "30887"

Test #9:

score: 5
Accepted
time: 16ms
memory: 16452kb

input:

10
1 2 15606
3 1 2777
4 3 2008
1 5 29898
1 6 31457
7 5 4630
6 8 32496
3 9 27660
10 9 29090
4
9 5 10 3

output:

56750

result:

ok 1 number(s): "56750"

Test #10:

score: 5
Accepted
time: 1458ms
memory: 37436kb

input:

50000
1 2 471
3 1 977
4 1 282
5 1 896
1 6 445
7 1 588
1 8 490
1 9 414
10 1 639
1 11 480
1 12 992
1 1...

output:

1000

result:

ok 1 number(s): "1000"

Test #11:

score: 5
Accepted
time: 564ms
memory: 36192kb

input:

57827
54932 3978 441741875
14421 41341 951021367
16486 9432 198653534
28422 37161 511342350
36408 32...

output:

4283776142

result:

ok 1 number(s): "4283776142"

Test #12:

score: 5
Accepted
time: 674ms
memory: 38836kb

input:

64505
59283 38674 557297696
50088 36058 633015257
55227 36689 644296377
37705 56843 51211994
5892 36...

output:

5656474206

result:

ok 1 number(s): "5656474206"

Test #13:

score: 5
Accepted
time: 775ms
memory: 41596kb

input:

71183
63870 7911 525337099
35984 32000 462525564
7688 29564 90004758
40886 25472 443696290
64424 855...

output:

5225064814

result:

ok 1 number(s): "5225064814"

Test #14:

score: 5
Accepted
time: 930ms
memory: 43348kb

input:

88063
50504 36851 657625071
75058 48169 905787538
86018 33103 31865446
48376 40101 629095717
79693 3...

output:

5956147249

result:

ok 1 number(s): "5956147249"

Test #15:

score: 5
Accepted
time: 1060ms
memory: 45720kb

input:

96849
88365 66816 659096010
8015 11647 110317598
78343 81013 322591398
43109 83812 312508510
85239 5...

output:

8837021296

result:

ok 1 number(s): "8837021296"

Test #16:

score: 5
Accepted
time: 999ms
memory: 48940kb

input:

95847
88538 69100 742724001
70805 51462 621821794
2085 11778 213909855
57449 38523 244862450
29965 3...

output:

5216694632

result:

ok 1 number(s): "5216694632"

Test #17:

score: 5
Accepted
time: 1812ms
memory: 60792kb

input:

152515
56687 13534 958639965
33468 14907 724071614
137373 98814 47187302
88952 84252 362681353
22362...

output:

4557578308

result:

ok 1 number(s): "4557578308"

Test #18:

score: 5
Accepted
time: 2811ms
memory: 82584kb

input:

226885
47596 120336 25535805
43532 34142 474242190
1274 226862 737255215
64173 77713 797054694
63990...

output:

8868374340

result:

ok 1 number(s): "8868374340"

Test #19:

score: 5
Accepted
time: 2783ms
memory: 86828kb

input:

240333
75075 217856 28510450
107016 167727 883367844
44984 73230 171125167
171171 88622 163847512
21...

output:

12416599265

result:

ok 1 number(s): "12416599265"

Test #20:

score: 5
Accepted
time: 4068ms
memory: 103024kb

input:

300000
113951 124761 112138441
18818 277839 394872041
73197 282077 209927273
79545 174586 243685102
...

output:

12484069034

result:

ok 1 number(s): "12484069034"