Submission #525300

#	Time	Username	Problem	Language	Result	Execution time	Memory
525300		benedict0724	Firefighting (NOI20_firefighting)	C++17	3 / 100	275 ms	42016 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];
int ans = 0;

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

        ds = min(ds, P);
        dl = max(dl, P);
    }

    if(dl + ds <= 0)
    {
        if(x == 1 || d - ds > k)
        {
            chk[x] = 1;
            ans++;
            return max(0LL, k-d);
        }
        return ds - d;
    }

    if(dl - d >= 0) return dl - d;
    return 0;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> k;
    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:53:8: warning: unused variable 'P' [-Wunused-variable]
   53 |     ll P = dfs(1, 0, 0);
      |        ^

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