Submission #524115

#	Time	Username	Problem	Language	Result	Execution time	Memory
524115		qwerasdfzxcl	Firefighting (NOI20_firefighting)	C++14	100 / 100	1611 ms	196860 KiB

Firefighting

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<pair<int, ll>> adj[300300];
pair<int, ll> sp[300300][20];
ll dep[300300];
priority_queue<pair<ll, int>> pq;

struct Cent{
    ll dist[300300][20], mn[300300];
    int cpa[300300], sz[300300], cdep[300300];
    bool visited[300300];

    int getsz(int s, int pa = -1){
        sz[s] = 1;
        for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa) sz[s] += getsz(v, s);
        return sz[s];
    }
    int getcent(int s, int cap, int pa = -1){
        for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa && sz[v]*2>cap) return getcent(v, cap, s);
        return s;
    }
    void getdist(int s, int dep, int pa = 0){
        for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa){
            dist[v][dep] = dist[s][dep] + w;
            getdist(v, dep, s);
        }
    }

    int init(int s, int dep = 0){
        getsz(s);
        int cent = getcent(s, sz[s]);

        cdep[cent] = dep;
        getdist(cent, dep);
        visited[cent] = 1;
        mn[cent] = 1e18;

        for (auto &[v, w]:adj[cent]) if (!visited[v]){
            int nxt = init(v, dep+1);
            cpa[nxt] = cent;
        }
        return cent;
    }

    void update(int s){
        for (int cur=s;cur;cur=cpa[cur]){
            mn[cur] = min(mn[cur], dist[s][cdep[cur]]);
        }
    }

    ll query(int s){
        ll ret = 1e18;
        for (int cur=s;cur;cur=cpa[cur]){
            ret = min(ret, dist[s][cdep[cur]] + mn[cur]);
        }
        return ret;
    }
}cent;

void dfs(int s, int pa = -1){
    for (auto &v:adj[s]) if (v.first!=pa){
        sp[v.first][0] = {s, v.second};
        dep[v.first] = dep[s] + v.second;
        dfs(v.first, s);
    }
}

void sp_init(int n){
    for (int j=1;j<20;j++){
        for (int i=1;i<=n;i++){
            sp[i][j].first = sp[sp[i][j-1].first][j-1].first;
            sp[i][j].second = sp[i][j-1].second + sp[sp[i][j-1].first][j-1].second;
        }
    }
}

int main(){
    int n;
    ll D;
    scanf("%d %lld", &n, &D);
    for (int i=0;i<n-1;i++){
        int x, y;
        ll z;
        scanf("%d %d %lld", &x, &y, &z);
        adj[x].emplace_back(y, z);
        adj[y].emplace_back(x, z);
    }
    if (n==1) {printf("1\n1\n"); return 0;}

    dfs(1);
    for (int i=1;i<=n;i++) pq.emplace(dep[i], i);

    cent.init(1);
    sp_init(n);

    vector<int> ans;
    while(!pq.empty()){
        auto cur = pq.top(); pq.pop();
        if (cent.query(cur.second) <= D) continue;

        int s = cur.second;
        ll rem = D;
        for (int j=19;j>=0;j--) if (sp[s][j].first && sp[s][j].second<=rem){
            rem -= sp[s][j].second;
            s = sp[s][j].first;
        }

        ans.push_back(s);
        cent.update(s);
    }

    printf("%d\n", (int)ans.size());
    for (auto &x:ans) printf("%d ", x);
    return 0;
}

Compilation message (stderr)

Firefighting.cpp: In member function 'int Cent::getsz(int, int)':
Firefighting.cpp:17:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |         for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa) sz[s] += getsz(v, s);
      |                    ^
Firefighting.cpp: In member function 'int Cent::getcent(int, int, int)':
Firefighting.cpp:21:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |         for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa && sz[v]*2>cap) return getcent(v, cap, s);
      |                    ^
Firefighting.cpp: In member function 'void Cent::getdist(int, int, int)':
Firefighting.cpp:25:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |         for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa){
      |                    ^
Firefighting.cpp: In member function 'int Cent::init(int, int)':
Firefighting.cpp:40:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |         for (auto &[v, w]:adj[cent]) if (!visited[v]){
      |                    ^
Firefighting.cpp: In function 'int main()':
Firefighting.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     scanf("%d %lld", &n, &D);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Firefighting.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d %d %lld", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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