Submission #1082691

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1082691	2024-09-01T07:32:17 Z	vjudge1	Firefighting (NOI20_firefighting)	C++17	100 / 100	170 ms	43496 KB

Firefighting

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 55);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int N, K;
#define MAX                 300005

struct Edge{
    int u, v, w;
    Edge(){}
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){}

    int other(int x){
        return (x ^ u ^ v);
    }
} edge[MAX];
vector<int> G[MAX];
vector<int> ret;
pair<bool, int> dfs(int u, int p, int last_w){
    int mx = -INF, mn = 0;

    //mx khoảng đỉnh xa nhất có thể được bao phủ bởi 1 trạm nằm trong cây con gốc u
    //mn khoảng cách xa nhất của đỉnh chưa được bao phủ nằm trong cây con gốc u

    for (int&i : G[u]){
        int v = edge[i].other(u);
        if(v ^ p){
            pair<int, int> x = dfs(v, u, edge[i].w);
            if (x.first == 0) maximize(mn, x.second);
            else maximize(mx, x.second);
        }
    }
    if (mx >= mn){
        if(mx - last_w < 0) return make_pair(0, 0);
        return make_pair(1, mx - last_w);
    }
    else{
        if (mn + last_w > K){
            ret.push_back(u);
            if(K - last_w < 0){
                return make_pair(0, 0);
            }
            return make_pair(1, K - last_w);
        }
        else{
            return make_pair(0, mn + last_w);
        }
    }
}
void process(void){
    cin >> N >> K;
    for (int i = 1; i < N; ++i){
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
        G[edge[i].u].emplace_back(i);
        G[edge[i].v].emplace_back(i);
    }
    dfs(1, 0, INF);
    cout << (int)ret.size() << '\n';
    for (int&i : ret) cout << i << " ";
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    process();
    return (0 ^ 0);
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	160 ms	29884 KB	Output is correct
2	Correct	169 ms	29880 KB	Output is correct
3	Correct	53 ms	15824 KB	Output is correct
4	Correct	153 ms	29364 KB	Output is correct
5	Correct	3 ms	7256 KB	Output is correct
6	Correct	3 ms	7260 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	7256 KB	Output is correct
2	Correct	3 ms	7516 KB	Output is correct
3	Correct	5 ms	7260 KB	Output is correct
4	Correct	5 ms	7260 KB	Output is correct
5	Correct	4 ms	7452 KB	Output is correct
6	Correct	4 ms	7260 KB	Output is correct
7	Correct	3 ms	7260 KB	Output is correct
8	Correct	3 ms	7516 KB	Output is correct
9	Correct	3 ms	7340 KB	Output is correct
10	Correct	3 ms	7256 KB	Output is correct
11	Correct	3 ms	7260 KB	Output is correct
12	Correct	4 ms	7384 KB	Output is correct
13	Correct	3 ms	7260 KB	Output is correct
14	Correct	3 ms	7260 KB	Output is correct
15	Correct	3 ms	7512 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	7260 KB	Output is correct
2	Correct	3 ms	7260 KB	Output is correct
3	Correct	3 ms	7256 KB	Output is correct
4	Correct	3 ms	7260 KB	Output is correct
5	Correct	3 ms	7260 KB	Output is correct
6	Correct	4 ms	7256 KB	Output is correct
7	Correct	3 ms	7260 KB	Output is correct
8	Correct	3 ms	7516 KB	Output is correct
9	Correct	3 ms	7508 KB	Output is correct
10	Correct	3 ms	7260 KB	Output is correct
11	Correct	3 ms	7260 KB	Output is correct
12	Correct	3 ms	7260 KB	Output is correct
13	Correct	3 ms	7260 KB	Output is correct
14	Correct	4 ms	7512 KB	Output is correct
15	Correct	3 ms	7256 KB	Output is correct
16	Correct	3 ms	7392 KB	Output is correct
17	Correct	3 ms	7260 KB	Output is correct
18	Correct	3 ms	7260 KB	Output is correct
19	Correct	3 ms	7260 KB	Output is correct
20	Correct	3 ms	7516 KB	Output is correct
21	Correct	3 ms	7260 KB	Output is correct
22	Correct	3 ms	7260 KB	Output is correct
23	Correct	3 ms	7516 KB	Output is correct
24	Correct	4 ms	7260 KB	Output is correct
25	Correct	5 ms	7516 KB	Output is correct
26	Correct	3 ms	7260 KB	Output is correct

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	163 ms	29984 KB	Output is correct
2	Correct	68 ms	18892 KB	Output is correct
3	Correct	77 ms	19204 KB	Output is correct
4	Correct	60 ms	17612 KB	Output is correct
5	Correct	3 ms	7260 KB	Output is correct
6	Correct	3 ms	7260 KB	Output is correct
7	Correct	115 ms	28000 KB	Output is correct
8	Correct	114 ms	28092 KB	Output is correct
9	Correct	116 ms	28096 KB	Output is correct
10	Correct	115 ms	28092 KB	Output is correct
11	Correct	160 ms	29880 KB	Output is correct
12	Correct	86 ms	21964 KB	Output is correct
13	Correct	51 ms	16524 KB	Output is correct
14	Correct	86 ms	20944 KB	Output is correct
15	Correct	102 ms	23688 KB	Output is correct
16	Correct	105 ms	24772 KB	Output is correct
17	Correct	105 ms	21968 KB	Output is correct
18	Correct	91 ms	21708 KB	Output is correct

Subtask #5
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7512 KB	Output is correct
2	Correct	4 ms	7676 KB	Output is correct
3	Correct	3 ms	7516 KB	Output is correct
4	Correct	4 ms	7516 KB	Output is correct
5	Correct	4 ms	7768 KB	Output is correct
6	Correct	5 ms	7708 KB	Output is correct
7	Correct	4 ms	7772 KB	Output is correct
8	Correct	3 ms	7644 KB	Output is correct
9	Correct	4 ms	7780 KB	Output is correct
10	Correct	4 ms	7772 KB	Output is correct
11	Correct	5 ms	7776 KB	Output is correct
12	Correct	4 ms	7428 KB	Output is correct
13	Correct	4 ms	7772 KB	Output is correct
14	Correct	4 ms	7768 KB	Output is correct
15	Correct	4 ms	7516 KB	Output is correct
16	Correct	3 ms	7516 KB	Output is correct
17	Correct	3 ms	7516 KB	Output is correct
18	Correct	4 ms	7516 KB	Output is correct
19	Correct	4 ms	7516 KB	Output is correct
20	Correct	4 ms	7516 KB	Output is correct
21	Correct	5 ms	7516 KB	Output is correct

Subtask #6
38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	137 ms	25172 KB	Output is correct
2	Correct	120 ms	24144 KB	Output is correct
3	Correct	137 ms	25424 KB	Output is correct
4	Correct	52 ms	15696 KB	Output is correct
5	Correct	170 ms	39108 KB	Output is correct
6	Correct	162 ms	37828 KB	Output is correct
7	Correct	161 ms	42124 KB	Output is correct
8	Correct	161 ms	40896 KB	Output is correct
9	Correct	138 ms	34764 KB	Output is correct
10	Correct	148 ms	33996 KB	Output is correct
11	Correct	167 ms	43496 KB	Output is correct
12	Correct	87 ms	19536 KB	Output is correct
13	Correct	156 ms	36452 KB	Output is correct
14	Correct	143 ms	31948 KB	Output is correct
15	Correct	125 ms	25680 KB	Output is correct
16	Correct	120 ms	24404 KB	Output is correct
17	Correct	128 ms	24144 KB	Output is correct
18	Correct	132 ms	25424 KB	Output is correct
19	Correct	84 ms	20052 KB	Output is correct
20	Correct	55 ms	14760 KB	Output is correct
21	Correct	134 ms	25544 KB	Output is correct

Submission #1082691

Compilation message

Subtask #1 3.0 / 3.0

Subtask #2 5.0 / 5.0

Subtask #3 9.0 / 9.0

Subtask #4 19.0 / 19.0

Subtask #5 26.0 / 26.0

Subtask #6 38.0 / 38.0

Subtask #1
3.0 / 3.0

Subtask #2
5.0 / 5.0

Subtask #3
9.0 / 9.0

Subtask #4
19.0 / 19.0

Subtask #5
26.0 / 26.0

Subtask #6
38.0 / 38.0