Submission #524286

#	Time	Username	Problem	Language	Result	Execution time	Memory
524286		79brue	Firefighting (NOI20_firefighting)	C++14	100 / 100	1732 ms	97400 KiB

Firefighting

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n; ll k;
vector<pair<int, ll> > link[300002];

int sz[300002];
bool centroidUsed[300002];
int centroidPar[300002];
vector<int> centroidChild[300002];
int depth[300002];
ll dist[300002];
int par[300002];
int LCADB[300002][22];
ll radius[300002];

vector<int> ans;

void setSize(int x, int par = -1){
    sz[x] = 1;
    for(auto y: link[x]){
        if(y.first == par || centroidUsed[y.first]) continue;
        setSize(y.first, x);
        sz[x] += sz[y.first];
    }
}

void dfs(int x, int p = -1){
    for(auto y: link[x]){
        if(y.first == p) continue;
        depth[y.first] = depth[x] + 1;
        LCADB[y.first][0] = par[y.first] = x;
        dist[y.first] = dist[x] + y.second;
        dfs(y.first, x);
    }
}

int getLCA(int x, int y){
    if(depth[x] < depth[y]) swap(x, y);
    for(int i=0; i<20; i++) if((depth[x] - depth[y]) & (1<<i)) x = LCADB[x][i];
    if(x==y) return x;
    for(int i=19; i>=0; i--) if(LCADB[x][i] != LCADB[y][i]) x = LCADB[x][i], y = LCADB[y][i];
    return par[x];
}

ll far(int x, int y){
    return dist[x] + dist[y] - dist[getLCA(x, y)] * 2;
}

int findCentroid(int x, int s, int par = -1){
    for(auto y: link[x]){
        if(y.first == par || centroidUsed[y.first]) continue;
        if(sz[y.first] > s/2) return findCentroid(y.first, s, x);
    }
    return x;
}

int centroidDecomposition(int x){
    setSize(x);
    int c = findCentroid(x, sz[x]);
    centroidUsed[c] = 1;

    for(auto y: link[c]){
        if(centroidUsed[y.first]) continue;
        int node = centroidDecomposition(y.first);
        centroidPar[node] = c;
        centroidChild[c].push_back(node);
    }
    return c;
}

bool alreadyUsed(int x){
    int root = x;
    while(root){
        if(far(root, x) <= radius[root]) return true;
        root = centroidPar[root];
    }
    return false;
}

void mark(int x){
    ans.push_back(x);
    int root = x;
    while(root){
        radius[root] = max(radius[root], k - far(root, x));
        root = centroidPar[root];
    }
}

int main(){
    scanf("%d %lld", &n, &k);
    for(int i=1; i<n; i++){
        int x, y; ll v;
        scanf("%d %d %lld", &x, &y, &v);
        link[x].push_back(make_pair(y, v));
        link[y].push_back(make_pair(x, v));
    }
    for(int i=1; i<=n; i++) radius[i] = -1;

    dfs(1);
    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
    centroidDecomposition(1);

    vector<pair<ll, int> > vec;
    for(int i=1; i<=n; i++) vec.push_back(make_pair(dist[i], i));
    sort(vec.rbegin(), vec.rend());

    for(pair<ll, int> p: vec){
        int x = p.second;
        if(alreadyUsed(x)) continue;

        int px = x;
        for(int d=19; d>=0; d--){
            if(LCADB[px][d] == 0) continue;
            if(far(LCADB[px][d], x) > k) continue;
            px = LCADB[px][d];
        }
        mark(px);
    }

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

Compilation message (stderr)

Firefighting.cpp: In function 'int main()':
Firefighting.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%d %lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Firefighting.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         scanf("%d %d %lld", &x, &y, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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