oj.uz

답안 #691274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
691274 2023-01-31T04:16:07 Z ghostwriter Firefighting (NOI20_firefighting) C++17
100 / 100
 355 ms 47396 KB 
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define bg begin
#define ed end
#define ft front
#define bk back
#define sz(x) (int)(x).size()
#define all(x) (x).bg(), (x).ed()
#define mtp make_tuple
#define ins insert
#define ers erase
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define str string
#define pi pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { WHILE(b) { a %= b; swap(a, b); } return b; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
const ll oo = 1e18 + 5;
const int N = 3e5 + 5;
int n;
vpi adj[N];
ll k;
vi ans;
pll dfs(int u, int p) {
    int pw = 0;
    vpll a;
    EACH(j, adj[u]) {
        int v = j.st, w = j.nd;
        if (v == p) {
            pw = w;
            continue;
        }
        a.pb(dfs(v, u));
        a.bk().st += w;
        a.bk().nd += w;
    }
    pll min1 = {oo, oo}, min2 = {oo, oo};
    EACH(j, a)
        if (j < min1) {
            min2 = min1;
            min1 = j;
        }
        else min2 = min(min2, j);
    pll rm = {oo, -oo};
    EACH(j, a) {
        pll tmp = (j == min1? min2 : min1);
        if (tmp.st + j.nd <= k) continue;
        rm.st = min(rm.st, j.st);
        rm.nd = max(rm.nd, j.nd);
    }
    if (rm.nd < -1e17) {
        if (min1.st <= k) return {min1.st, rm.nd};
        if (p && pw <= k) return {min1.st, max(0LL, rm.nd)};
        ans.pb(u);
        return {0, -oo};
    }
    else {
        if (p && rm.nd + pw <= k) return {min1.st, rm.nd};
        ans.pb(u);
        return {0LL, -oo};
    }
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen(file".inp", "r", stdin);
//    freopen(file".out", "w", stdout);
    cin >> n >> k;
    FRN(i, n - 1) {
        int a, b, d;
        cin >> a >> b >> d;
        adj[a].pb({b, d});
        adj[b].pb({a, d});
    }
    dfs(1, 0);
    cout << sz(ans) << '\n';
    EACH(i, ans) cout << i << (i == ans.bk()? "\n" : " ");
    return 0;
}
/*
5 1
5 3 3
3 2 3
5 1 2
5 4 1

*/

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 317 ms 28552 KB Output is correct
2 Correct 355 ms 28424 KB Output is correct
3 Correct 99 ms 15144 KB Output is correct
4 Correct 325 ms 27920 KB Output is correct
5 Correct 5 ms 7252 KB Output is correct
6 Correct 5 ms 7252 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7368 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7368 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 4 ms 7360 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 6 ms 7368 KB Output is correct
11 Correct 4 ms 7252 KB Output is correct
12 Correct 5 ms 7376 KB Output is correct
13 Correct 4 ms 7372 KB Output is correct
14 Correct 5 ms 7376 KB Output is correct
15 Correct 5 ms 7372 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7252 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 5 ms 7252 KB Output is correct
4 Correct 6 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7368 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 5 ms 7376 KB Output is correct
11 Correct 5 ms 7368 KB Output is correct
12 Correct 5 ms 7260 KB Output is correct
13 Correct 4 ms 7376 KB Output is correct
14 Correct 4 ms 7252 KB Output is correct
15 Correct 4 ms 7372 KB Output is correct
16 Correct 4 ms 7372 KB Output is correct
17 Correct 5 ms 7368 KB Output is correct
18 Correct 5 ms 7372 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 5 ms 7252 KB Output is correct
21 Correct 4 ms 7252 KB Output is correct
22 Correct 5 ms 7316 KB Output is correct
23 Correct 6 ms 7376 KB Output is correct
24 Correct 5 ms 7368 KB Output is correct
25 Correct 4 ms 7252 KB Output is correct
26 Correct 4 ms 7324 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 28472 KB Output is correct
2 Correct 151 ms 17228 KB Output is correct
3 Correct 134 ms 17396 KB Output is correct
4 Correct 108 ms 16072 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 229 ms 28920 KB Output is correct
8 Correct 246 ms 28708 KB Output is correct
9 Correct 252 ms 28860 KB Output is correct
10 Correct 233 ms 28904 KB Output is correct
11 Correct 308 ms 28584 KB Output is correct
12 Correct 191 ms 19632 KB Output is correct
13 Correct 101 ms 14912 KB Output is correct
14 Correct 156 ms 18908 KB Output is correct
15 Correct 200 ms 21296 KB Output is correct
16 Correct 214 ms 22248 KB Output is correct
17 Correct 199 ms 19924 KB Output is correct
18 Correct 162 ms 19536 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7508 KB Output is correct
2 Correct 6 ms 7512 KB Output is correct
3 Correct 5 ms 7416 KB Output is correct
4 Correct 7 ms 7436 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 6 ms 7636 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 6 ms 7636 KB Output is correct
9 Correct 5 ms 7636 KB Output is correct
10 Correct 5 ms 7636 KB Output is correct
11 Correct 5 ms 7696 KB Output is correct
12 Correct 6 ms 7380 KB Output is correct
13 Correct 6 ms 7636 KB Output is correct
14 Correct 7 ms 7636 KB Output is correct
15 Correct 5 ms 7508 KB Output is correct
16 Correct 5 ms 7384 KB Output is correct
17 Correct 4 ms 7384 KB Output is correct
18 Correct 5 ms 7500 KB Output is correct
19 Correct 6 ms 7388 KB Output is correct
20 Correct 4 ms 7380 KB Output is correct
21 Correct 5 ms 7532 KB Output is correct

Subtask #6
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 247 ms 24608 KB Output is correct
2 Correct 236 ms 23884 KB Output is correct
3 Correct 271 ms 24996 KB Output is correct
4 Correct 116 ms 15436 KB Output is correct
5 Correct 317 ms 40136 KB Output is correct
6 Correct 291 ms 37760 KB Output is correct
7 Correct 269 ms 44892 KB Output is correct
8 Correct 305 ms 43304 KB Output is correct
9 Correct 297 ms 35380 KB Output is correct
10 Correct 267 ms 34196 KB Output is correct
11 Correct 300 ms 47396 KB Output is correct
12 Correct 171 ms 19260 KB Output is correct
13 Correct 302 ms 37160 KB Output is correct
14 Correct 284 ms 32536 KB Output is correct
15 Correct 301 ms 25392 KB Output is correct
16 Correct 252 ms 24108 KB Output is correct
17 Correct 265 ms 23988 KB Output is correct
18 Correct 301 ms 25224 KB Output is correct
19 Correct 179 ms 19836 KB Output is correct
20 Correct 127 ms 14412 KB Output is correct
21 Correct 286 ms 25272 KB Output is correct