ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#417 | #54. 「NOIP2012」疫情控制 | Pigsyy | 100 | 18742ms | 116372kb | C++23 | 11.4kb | 2025-04-24 11:28:42 | 2025-04-24 11:42:23 |
answer
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using i64 = long long;
using pii = pair<int, i64>;
namespace Fread {
const int SIZE = 1 << 16;
char buf[SIZE], *S, *T;
inline char getchar() {
if (S == T) {
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T)
return '\n';
}
return *S++;
}
}
using namespace Fread;
namespace Fwrite {
const int SIZE = 1 << 16;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c) {
*S++ = c;
if (S == T)
flush();
}
struct NTR {
~NTR() {
flush();
}
} ztr;
}
using namespace Fwrite;
#define getchar Fread::getchar
#define putchar Fwrite::putchar
namespace Fastio {
struct Reader {
template <typename T> Reader &operator >> (T &x) {
x = 0;
short f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-')
f *= -1;
c = getchar();
}
while (c >= '0' && c <= '9')
x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
x *= f;
return *this;
}
Reader &operator >> (double &x) {
x = 0;
double t = 0;
short f = 1, s = 0;
char c = getchar();
while ((c < '0' || c > '9') && c != '.') {
if (c == '-')
f *= -1;
c = getchar();
}
while (c >= '0' && c <= '9' && c != '.')
x = x * 10 + (c ^ 48), c = getchar();
if (c == '.')
c = getchar();
else {
x *= f;
return *this;
}
while (c >= '0' && c <= '9')
t = t * 10 + (c ^ 48), s++, c = getchar();
while (s--)
t /= 10.0;
x = (x + t) * f;
return *this;
}
Reader &operator >> (long double &x) {
x = 0;
long double t = 0;
short f = 1, s = 0;
char c = getchar();
while ((c < '0' || c > '9') && c != '.') {
if (c == '-')
f *= -1;
c = getchar();
}
while (c >= '0' && c <= '9' && c != '.')
x = x * 10 + (c ^ 48), c = getchar();
if (c == '.')
c = getchar();
else {
x *= f;
return *this;
}
while (c >= '0' && c <= '9')
t = t * 10 + (c ^ 48), s++, c = getchar();
while (s--)
t /= 10.0;
x = (x + t) * f;
return *this;
}
Reader &operator >> (__float128 &x) {
x = 0;
__float128 t = 0;
short f = 1, s = 0;
char c = getchar();
while ((c < '0' || c > '9') && c != '.') {
if (c == '-')
f *= -1;
c = getchar();
}
while (c >= '0' && c <= '9' && c != '.')
x = x * 10 + (c ^ 48), c = getchar();
if (c == '.')
c = getchar();
else {
x *= f;
return *this;
}
while (c >= '0' && c <= '9')
t = t * 10 + (c ^ 48), s++, c = getchar();
while (s--)
t /= 10.0;
x = (x + t) * f;
return *this;
}
Reader &operator >> (char &c) {
c = getchar();
while (c == ' ' || c == '\n' || c == '\r')
c = getchar();
return *this;
}
Reader &operator >> (char *str) {
int len = 0;
char c = getchar();
while (c == ' ' || c == '\n' || c == '\r')
c = getchar();
while (c != ' ' && c != '\n' && c != '\r')
str[len++] = c, c = getchar();
str[len] = '\0';
return *this;
}
Reader &operator >> (string &str) {
str.clear();
char c = getchar();
while (c == ' ' || c == '\n' || c == '\r')
c = getchar();
while (c != ' ' && c != '\n' && c != '\r')
str.push_back(c), c = getchar();
return *this;
}
Reader() {}
} cin;
const char endl = '\n';
struct Writer {
const int Setprecision = 6;
typedef int mxdouble;
template <typename T> Writer &operator << (T x) {
if (x == 0) {
putchar('0');
return *this;
}
if (x < 0)
putchar('-'), x = -x;
static short sta[40];
short top = 0;
while (x > 0)
sta[++top] = x % 10, x /= 10;
while (top > 0)
putchar(sta[top] + '0'), top--;
return *this;
}
Writer &operator << (double x) {
if (x < 0)
putchar('-'), x = -x;
mxdouble _ = x;
x -= (double)_;
static short sta[40];
short top = 0;
while (_ > 0)
sta[++top] = _ % 10, _ /= 10;
if (top == 0)
putchar('0');
while (top > 0)
putchar(sta[top] + '0'), top--;
putchar('.');
for (int i = 0; i < Setprecision; i++)
x *= 10;
_ = x;
while (_ > 0)
sta[++top] = _ % 10, _ /= 10;
for (int i = 0; i < Setprecision - top; i++)
putchar('0');
while (top > 0)
putchar(sta[top] + '0'), top--;
return *this;
}
Writer &operator << (long double x) {
if (x < 0)
putchar('-'), x = -x;
mxdouble _ = x;
x -= (long double)_;
static short sta[40];
short top = 0;
while (_ > 0)
sta[++top] = _ % 10, _ /= 10;
if (top == 0)
putchar('0');
while (top > 0)
putchar(sta[top] + '0'), top--;
putchar('.');
for (int i = 0; i < Setprecision; i++)
x *= 10;
_ = x;
while (_ > 0)
sta[++top] = _ % 10, _ /= 10;
for (int i = 0; i < Setprecision - top; i++)
putchar('0');
while (top > 0)
putchar(sta[top] + '0'), top--;
return *this;
}
Writer &operator << (__float128 x) {
if (x < 0)
putchar('-'), x = -x;
mxdouble _ = x;
x -= (__float128)_;
static short sta[40];
short top = 0;
while (_ > 0)
sta[++top] = _ % 10, _ /= 10;
if (top == 0)
putchar('0');
while (top > 0)
putchar(sta[top] + '0'), top--;
putchar('.');
for (int i = 0; i < Setprecision; i++)
x *= 10;
_ = x;
while (_ > 0)
sta[++top] = _ % 10, _ /= 10;
for (int i = 0; i < Setprecision - top; i++)
putchar('0');
while (top > 0)
putchar(sta[top] + '0'), top--;
return *this;
}
Writer &operator << (char c) {
putchar(c);
return *this;
}
Writer &operator << (char *str) {
int cur = 0;
while (str[cur])
putchar(str[cur++]);
return *this;
}
Writer &operator << (const char *str) {
int cur = 0;
while (str[cur])
putchar(str[cur++]);
return *this;
}
Writer &operator << (string str) {
int st = 0, ed = str.size();
while (st < ed)
putchar(str[st++]);
return *this;
}
Writer() {}
} cout;
}
using namespace Fastio;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
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];
std::vector<pii> g[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() {
// freopen("blockade20.in", "r", stdin);
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i < n; i ++) {
int a, b, c;
cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
}
for (int i = 1; i <= n; i ++)
for (auto [j, k] : g[i])
add(i, j, k);
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];
// dfs2(rt, rt);
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: 10ms
memory: 19780kb
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: 9ms
memory: 20004kb
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: 16324kb
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: 16256kb
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: 22ms
memory: 20232kb
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: 9ms
memory: 16684kb
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: 48ms
memory: 24380kb
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: 53ms
memory: 24452kb
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: 15ms
memory: 19952kb
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: 1397ms
memory: 42636kb
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: 556ms
memory: 39196kb
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: 640ms
memory: 42020kb
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: 756ms
memory: 44724kb
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: 948ms
memory: 50276kb
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: 1071ms
memory: 53176kb
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: 1047ms
memory: 53172kb
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: 1883ms
memory: 70672kb
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: 3031ms
memory: 97888kb
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: 2960ms
memory: 97252kb
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: 4248ms
memory: 116372kb
input:
300000 113951 124761 112138441 18818 277839 394872041 73197 282077 209927273 79545 174586 243685102 ...
output:
12484069034
result:
ok 1 number(s): "12484069034"