답안 #524281

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524281	2022-02-09T01:55:09 Z	79brue	Firefighting (NOI20_firefighting)	C++14	0 / 100	1052 ms	1048580 KB

Firefighting

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

int sz[200002];
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) - 1);
        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);
    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

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
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	302 ms	129600 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	8 ms	14412 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	14396 KB	Output is correct
2	Correct	7 ms	14412 KB	Output is correct
3	Correct	7 ms	14404 KB	Output is correct
4	Incorrect	8 ms	14416 KB	Output isn't correct
5	Halted	0 ms	0 KB	-