Submission #737540

#	Time	Username	Problem	Language	Result	Execution time	Memory
737540		Ronin13	Firefighting (NOI20_firefighting)	C++14	100 / 100	2177 ms	272780 KiB

Firefighting

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 300001;
vector <vector <pll> > g(nmax);
int p[nmax][22];
ll d[nmax][22];
//ll len[nmax][22];
ll dp[nmax];
vector <vector <pll> > cent(nmax);
vector <ll> cur(nmax);

void dfs(int v, int e, ll last){
    p[v][0] = e;
    d[v][0] = last;
    for(int j = 1; j <= 20; j++){
        p[v][j] = p[p[v][j - 1]][j - 1];
        d[v][j] = d[v][j - 1] + d[p[v][j - 1]][j - 1];
    }
    for(auto x : g[v]){
        int to = x.f;
        if(to == e) continue;
        dp[to] = dp[v] + x.s;
        dfs(to, v, x.s);
    }
}

ll getlast(int v, ll k){
    for(int j = 20; j >= 0; j--){
        if(d[v][j] > k) continue;
        k -= d[v][j];
        v = p[v][j];
    }
    return v;
}

vector <int> sz(nmax);
vector <bool> marked(nmax);

void DFS(int v, int e){
    sz[v] = 1;
    for(auto ed : g[v]){
        int to = ed.f;
        if(to == e) continue;
        if(marked[to]) continue;
        DFS(to, v);
        sz[v] += sz[to];
    }
}


int find_cen(int v, int e, int n){
    for(auto ed : g[v]){
        int to = ed.f;
        if(to == e) continue;
        if(marked[to]) continue;
        if(sz[to] > n / 2){
            return find_cen(to, v, n);
        }
    }
    return v;
}


void DFS2(int v, int e, int lead, ll cur){
    cent[v].pb({lead, cur});
    for(auto x : g[v]){
        int to = x.f;
        if(to == e) continue;
        if(marked[to]) continue;
        DFS2(to, v, lead, cur + x.s);
    }
}

void upd(int v){
    for(auto to : cent[v]){
        cur[to.f] = min(cur[to.f], to.s);
    }
}

ll getans(int v){
    ll mn = 1e18;
    for(auto to : cent[v]){
        mn = min(mn, cur[to.f] + to.s);
    }
    return mn;
}

void decompose(int v){
    DFS(v, v);
    int x = find_cen(v, v, sz[v]);
    DFS2(x, x, x, 0);
    marked[x] = true;
    for(auto ed : g[x]){
        int to = ed.f;
        if(marked[to]) continue;
        decompose(to);
    }
}

int main(){
    int n; cin >> n;
    ll k; cin >> k;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        ll w; cin >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    for(int j= 0; j < 20; j++){
        d[0][j] = 1e12;
    }
    dfs(1, 1, 0);
    decompose(1);

    vector <pll> vec;
    for(int i= 1;i <= n; i++){
        vec.pb({dp[i], i});
    }
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    int cnt = 0;
    vector <int> ans;
    for(int i = 1; i <= n; i++){
        cur[i] = 1e18;
    }
    for(auto x : vec){
        int to = x.s;
        ll o = getans(to);
        if(o <= k){
            continue;
        }
        cnt++;
        int v = getlast(to, k);
        upd(v);
        ans.pb(v);
    }
    cout << cnt << "\n";
    for(int to : ans){
        cout<< to << ' ';
    }
    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