Logo Wy Online Judge

WyOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#417#54. 「NOIP2012」疫情控制Pigsyy10018742ms116372kbC++2311.4kb2025-04-24 11:28:422025-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"