Submission #525334

#	Time	Username	Problem	Language	Result	Execution time	Memory
525334		benedict0724	Firefighting (NOI20_firefighting)	C++17	100 / 100	321 ms	46368 KiB

Firefighting

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, ll> pi;
const ll INF = 1e18;
int n; ll k;

vector<pi> adj[300002];
bool chk[300002];
bool ou[300002];
int ans = 0;

ll dfs(int x, int p, ll d)
{
    ll ds = 0, dl = INF;
    for(auto u : adj[x])
    {
        int i = u.first;
        if(i == p) continue;
        ll c = u.second;
        ll P = dfs(i, x, c);

        if(!ou[i]) ds = max(ds, P);
        else dl = min(dl, P);
    }

    if(dl + ds > k)
    {
        if(x == 1 || d + ds > k)
        {
            chk[x] = 1; ou[x] = 1;
            ans++;
            return d;
        }
        ou[x] = 0;
        return ds + d;
    }

    if(dl + d > k) { ou[x] = 0; return 0; }
    ou[x] = 1;
    return dl + d;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> k;
    if(n == 1)
    {
        cout << "1\n1";
        return 0;
    }
    for(int i=1;i<n;i++)
    {
        int a, b; ll D; cin >> a >> b >> D;
        adj[a].push_back({b, D});
        adj[b].push_back({a, D});
    }

    ll P = dfs(1, 0, 0);

    cout << ans << "\n";

    for(int i=1;i<=n;i++) if(chk[i]) cout << i << " ";
}

Compilation message (stderr)

Firefighting.cpp: In function 'int main()':
Firefighting.cpp:61:8: warning: unused variable 'P' [-Wunused-variable]
   61 |     ll P = dfs(1, 0, 0);
      |        ^

• Subtask 1: 3 / 3
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26
• Subtask 6: 38 / 38