ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#409 | #54. 「NOIP2012」疫情控制 | Pigsyy | 80 | 14614ms | 99224kb | C++23 | 2.3kb | 2025-04-24 08:55:04 | 2025-04-24 11:40:41 |
answer
#include <bits/stdc++.h>
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];
i64 dist[maxn][20];
int vis[maxn], dp[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 dfs(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];
}
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;
dfs(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];
dfs(1);
i64 lo = 0, ro = 1e18;
while (lo <= ro) {
i64 mid = lo + ro >> 1;
memset(vis, 0, sizeof vis);
memset(dp, 0, sizeof dp);
for (int i = 1; i <= n; i ++)
rest[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<i64> usable;
for (int i = h[1]; ~i; i = ne[i]) {
int rt = e[i];
auto dfs = [&](auto dfs, int u) -> void {
if (u != rt) dp[u] = vis[u];
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa[u][0]) continue;
dfs(dfs, v);
dp[u] |= dp[v];
}
};
sort(rest[rt].begin(), rest[rt].end(), greater<int>());
if (!dp[rt]) {
if (rest[rt].size()) {
dp[rt] = 1;
rest[rt].pop_back();
}
}
for (auto t : rest[rt])
usable.insert(t - w[i]);
}
bool ok = true;
for (int i = h[1]; ~i; i = ne[i]) {
int u = e[i];
if (!dp[u]) {
auto it = usable.lower_bound(w[i]);
if (it == usable.end()) {
ok = false;
break;
}
usable.erase(it);
}
}
if (ok) ro = mid - 1;
else lo = mid + 1;
}
cout << ro + 1 << endl;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 0
Wrong Answer
time: 18ms
memory: 12644kb
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:
17
result:
wrong answer 1st numbers differ - expected: '9', found: '17'
Test #2:
score: 5
Accepted
time: 24ms
memory: 14732kb
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: 20ms
memory: 14380kb
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: 19ms
memory: 16080kb
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: 25ms
memory: 14160kb
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: 26ms
memory: 16332kb
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: 0
Wrong Answer
time: 34ms
memory: 18848kb
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:
88190
result:
wrong answer 1st numbers differ - expected: '80321', found: '88190'
Test #8:
score: 5
Accepted
time: 34ms
memory: 19212kb
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: 24ms
memory: 12780kb
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: 0
Wrong Answer
time: 724ms
memory: 32372kb
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:
1002
result:
wrong answer 1st numbers differ - expected: '1000', found: '1002'
Test #11:
score: 5
Accepted
time: 461ms
memory: 34472kb
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: 577ms
memory: 34848kb
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: 679ms
memory: 36868kb
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: 813ms
memory: 40944kb
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: 918ms
memory: 42364kb
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: 882ms
memory: 42340kb
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: 1505ms
memory: 58572kb
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: 2312ms
memory: 79156kb
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: 2247ms
memory: 82604kb
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: 0
Wrong Answer
time: 3272ms
memory: 99224kb
input:
300000 113951 124761 112138441 18818 277839 394872041 73197 282077 209927273 79545 174586 243685102 ...
output:
13277243966
result:
wrong answer 1st numbers differ - expected: '12484069034', found: '13277243966'