Submission #1082690

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1082690	2024-09-01T07:31:18 Z	Whisper	Firefighting (NOI20_firefighting)	C++17	100 / 100	184 ms	49348 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	173 ms	36796 KB	Output is correct
2	Correct	158 ms	36792 KB	Output is correct
3	Correct	62 ms	18120 KB	Output is correct
4	Correct	173 ms	36012 KB	Output is correct
5	Correct	3 ms	7516 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	7260 KB	Output is correct
2	Correct	3 ms	7516 KB	Output is correct
3	Correct	3 ms	7516 KB	Output is correct
4	Correct	3 ms	7516 KB	Output is correct
5	Correct	3 ms	7516 KB	Output is correct
6	Correct	4 ms	7260 KB	Output is correct
7	Correct	3 ms	7512 KB	Output is correct
8	Correct	4 ms	7516 KB	Output is correct
9	Correct	3 ms	7516 KB	Output is correct
10	Correct	3 ms	7516 KB	Output is correct
11	Correct	3 ms	7516 KB	Output is correct
12	Correct	3 ms	7260 KB	Output is correct
13	Correct	3 ms	7516 KB	Output is correct
14	Correct	3 ms	7516 KB	Output is correct
15	Correct	3 ms	7516 KB	Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	184 ms	36808 KB	Output is correct
2	Correct	75 ms	21452 KB	Output is correct
3	Correct	75 ms	21948 KB	Output is correct
4	Correct	65 ms	19944 KB	Output is correct
5	Correct	4 ms	7512 KB	Output is correct
6	Correct	3 ms	7516 KB	Output is correct
7	Correct	115 ms	32760 KB	Output is correct
8	Correct	145 ms	32700 KB	Output is correct
9	Correct	125 ms	32956 KB	Output is correct
10	Correct	129 ms	32956 KB	Output is correct
11	Correct	159 ms	36796 KB	Output is correct
12	Correct	89 ms	25036 KB	Output is correct
13	Correct	58 ms	18372 KB	Output is correct
14	Correct	84 ms	23900 KB	Output is correct
15	Correct	103 ms	27328 KB	Output is correct
16	Correct	123 ms	28876 KB	Output is correct
17	Correct	90 ms	25296 KB	Output is correct
18	Correct	90 ms	25032 KB	Output is correct

Subtask #5
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7768 KB	Output is correct
2	Correct	3 ms	7512 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	7772 KB	Output is correct
6	Correct	4 ms	7772 KB	Output is correct
7	Correct	4 ms	7772 KB	Output is correct
8	Correct	4 ms	7772 KB	Output is correct
9	Correct	5 ms	7772 KB	Output is correct
10	Correct	4 ms	7780 KB	Output is correct
11	Correct	4 ms	7772 KB	Output is correct
12	Correct	4 ms	7512 KB	Output is correct
13	Correct	5 ms	7772 KB	Output is correct
14	Correct	4 ms	7792 KB	Output is correct
15	Correct	5 ms	7768 KB	Output is correct
16	Correct	3 ms	7516 KB	Output is correct
17	Correct	3 ms	7516 KB	Output is correct
18	Correct	3 ms	7516 KB	Output is correct
19	Correct	4 ms	7524 KB	Output is correct
20	Correct	3 ms	7516 KB	Output is correct
21	Correct	4 ms	7768 KB	Output is correct

Subtask #6
38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	139 ms	31600 KB	Output is correct
2	Correct	133 ms	30448 KB	Output is correct
3	Correct	138 ms	32012 KB	Output is correct
4	Correct	63 ms	19024 KB	Output is correct
5	Correct	163 ms	44120 KB	Output is correct
6	Correct	175 ms	42664 KB	Output is correct
7	Correct	157 ms	46916 KB	Output is correct
8	Correct	160 ms	46008 KB	Output is correct
9	Correct	141 ms	39888 KB	Output is correct
10	Correct	166 ms	38868 KB	Output is correct
11	Correct	180 ms	49348 KB	Output is correct
12	Correct	85 ms	23892 KB	Output is correct
13	Correct	160 ms	41928 KB	Output is correct
14	Correct	175 ms	37996 KB	Output is correct
15	Correct	141 ms	32340 KB	Output is correct
16	Correct	134 ms	30800 KB	Output is correct
17	Correct	119 ms	30548 KB	Output is correct
18	Correct	145 ms	32344 KB	Output is correct
19	Correct	81 ms	24656 KB	Output is correct
20	Correct	63 ms	17232 KB	Output is correct
21	Correct	145 ms	32336 KB	Output is correct

Submission #1082690

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