Submission #1319048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319048		aryan	Firefighting (NOI20_firefighting)	C++20	14 / 100	99 ms	18272 KiB

Firefighting

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;


int main(){
        
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,k;
    cin >> n >> k;
    vector<vector<pair<int,int>>> adj(n);
    for(int i = 0;i < n - 1;i++){
        int u,v,w;
        cin >> u >> v >> w;
        u --;
        v --;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    assert(n <= 17);    

    const i64 inf = 1e18;
    vector<bool> is(n,false);
    vector<i64> sub(n,inf);
    function<void(int,int)> dfs1 = [&](int u,int p){
        if(is[u]) sub[u] = 0LL;
        for(auto pa : adj[u]){
            int v = pa.first;
            int w = pa.second;
            if(v == p) continue;
            dfs1(v,u);
            sub[u] = min(sub[u],sub[v] + w);
        }
    };

    vector<i64> dp(n,inf);
    function<void(int,int,i64)> dfs2 = [&](int u,int p,i64 mini){
        dp[u] = min(mini,sub[u]);
        for(auto pa : adj[u]){
            int v = pa.first;
            int w = pa.second;
            if(v == p) continue;
            dfs2(v,u,min(mini,sub[u]) + w);
        }
    };

    int best = (1 << n) - 1; 
    for(int i = 0;i < (1 << n);i++){
        for(int j = 0;j < n;j++){
            if(i & (1 << j)){
                is[j] = true;
            }else{
                is[j] = false;
            }
            sub[j] = dp[j] = inf;
        }
        dfs1(0,0);
        dfs2(0,0,inf);
        bool ok = true;
        for(int j = 0;j < n;j++){
            if(dp[j] > (i64)k){
                ok = false;
                break;
            }
        }
        if(ok && __builtin_popcount(i) < __builtin_popcount(best)){
            best = i;
        }
    }
    cout << __builtin_popcount(best) << '\n';
    for(int i = 0;i < n;i++){
        if((1 << i) & best){
            cout << i + 1 << " ";
        }
    }
    cout << '\n';

    return 0;
}

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