Submission #682564

#	Time	Username	Problem	Language	Result	Execution time	Memory
682564		raysh07	Firefighting (NOI20_firefighting)	C++17	100 / 100	300 ms	47456 KiB

Firefighting

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e5 + 69;
vector<pair<int, int>> adj[maxn];
bool type[maxn];
vector<int> ans;
int n, k;

int dfs(int c, int p, int len) 
{
    int ma = 0, mi = INF;
    for(auto n2 : adj[c]) {
        int n = n2.first;
        int d = n2.second;
        if(n==p) continue;
        int l = dfs(n, c, d);
        
        if(type[n]) mi = min(mi, l);
        else ma = max(ma, l);
    }
    
    if(mi + ma > k) {
        if(len == -1 || ma + len > k) {
            type[c] = true;
            ans.push_back(c);
            return len;
        }
        type[c] = false;
        return len + ma;
    }
    if(mi+len > k) {
        type[c] = false;
        return 0;
    }
    type[c] = true;
    return len + mi;
}

void Solve() 
{
    cin>>n>>k;
    for (int i=1; i<n; i++){
        int a, b, c;
        cin>>a>>b>>c;
        
        adj[a-1].push_back({b-1, c});
        adj[b-1].push_back({a-1, c});
    }
    
    dfs(0, -1, -1);
    cout<<ans.size()<<"\n";
    for (auto x: ans)cout<<x +1 <<" ";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 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