oj.uz

답안 #524286

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524286 2022-02-09T02:02:02 Z 79brue Firefighting (NOI20_firefighting) C++14
100 / 100
 1732 ms 97400 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1710 ms 79572 KB Output is correct
2 Correct 1732 ms 79656 KB Output is correct
3 Correct 481 ms 38320 KB Output is correct
4 Correct 1688 ms 77980 KB Output is correct
5 Correct 8 ms 14404 KB Output is correct
6 Correct 8 ms 14424 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14428 KB Output is correct
2 Correct 7 ms 14320 KB Output is correct
3 Correct 7 ms 14404 KB Output is correct
4 Correct 7 ms 14340 KB Output is correct
5 Correct 7 ms 14412 KB Output is correct
6 Correct 8 ms 14404 KB Output is correct
7 Correct 7 ms 14340 KB Output is correct
8 Correct 7 ms 14412 KB Output is correct
9 Correct 7 ms 14412 KB Output is correct
10 Correct 7 ms 14412 KB Output is correct
11 Correct 8 ms 14392 KB Output is correct
12 Correct 7 ms 14408 KB Output is correct
13 Correct 8 ms 14412 KB Output is correct
14 Correct 7 ms 14412 KB Output is correct
15 Correct 7 ms 14356 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 7 ms 14448 KB Output is correct
3 Correct 7 ms 14340 KB Output is correct
4 Correct 8 ms 14392 KB Output is correct
5 Correct 7 ms 14412 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 7 ms 14336 KB Output is correct
8 Correct 7 ms 14428 KB Output is correct
9 Correct 7 ms 14372 KB Output is correct
10 Correct 7 ms 14412 KB Output is correct
11 Correct 8 ms 14404 KB Output is correct
12 Correct 8 ms 14396 KB Output is correct
13 Correct 8 ms 14412 KB Output is correct
14 Correct 7 ms 14400 KB Output is correct
15 Correct 7 ms 14392 KB Output is correct
16 Correct 8 ms 14412 KB Output is correct
17 Correct 9 ms 14444 KB Output is correct
18 Correct 8 ms 14412 KB Output is correct
19 Correct 8 ms 14396 KB Output is correct
20 Correct 8 ms 14404 KB Output is correct
21 Correct 8 ms 14412 KB Output is correct
22 Correct 8 ms 14412 KB Output is correct
23 Correct 8 ms 14412 KB Output is correct
24 Correct 9 ms 14412 KB Output is correct
25 Correct 8 ms 14344 KB Output is correct
26 Correct 8 ms 14460 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1726 ms 79620 KB Output is correct
2 Correct 565 ms 50496 KB Output is correct
3 Correct 587 ms 54196 KB Output is correct
4 Correct 463 ms 49352 KB Output is correct
5 Correct 7 ms 14412 KB Output is correct
6 Correct 7 ms 14396 KB Output is correct
7 Correct 515 ms 82352 KB Output is correct
8 Correct 553 ms 82480 KB Output is correct
9 Correct 558 ms 82428 KB Output is correct
10 Correct 522 ms 82600 KB Output is correct
11 Correct 1727 ms 86500 KB Output is correct
12 Correct 854 ms 60760 KB Output is correct
13 Correct 473 ms 43308 KB Output is correct
14 Correct 774 ms 58256 KB Output is correct
15 Correct 950 ms 67516 KB Output is correct
16 Correct 1029 ms 71676 KB Output is correct
17 Correct 808 ms 62740 KB Output is correct
18 Correct 750 ms 61860 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14924 KB Output is correct
2 Correct 10 ms 15052 KB Output is correct
3 Correct 9 ms 14688 KB Output is correct
4 Correct 10 ms 14860 KB Output is correct
5 Correct 13 ms 15180 KB Output is correct
6 Correct 13 ms 15180 KB Output is correct
7 Correct 12 ms 15180 KB Output is correct
8 Correct 12 ms 15192 KB Output is correct
9 Correct 12 ms 15112 KB Output is correct
10 Correct 12 ms 15180 KB Output is correct
11 Correct 13 ms 15172 KB Output is correct
12 Correct 12 ms 14720 KB Output is correct
13 Correct 13 ms 15256 KB Output is correct
14 Correct 12 ms 15224 KB Output is correct
15 Correct 11 ms 15052 KB Output is correct
16 Correct 9 ms 14796 KB Output is correct
17 Correct 9 ms 14668 KB Output is correct
18 Correct 12 ms 15060 KB Output is correct
19 Correct 10 ms 14924 KB Output is correct
20 Correct 9 ms 14720 KB Output is correct
21 Correct 11 ms 15180 KB Output is correct

Subtask #6
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 859 ms 76004 KB Output is correct
2 Correct 1090 ms 80040 KB Output is correct
3 Correct 1216 ms 84412 KB Output is correct
4 Correct 438 ms 47248 KB Output is correct
5 Correct 1719 ms 93096 KB Output is correct
6 Correct 1693 ms 91728 KB Output is correct
7 Correct 1565 ms 95928 KB Output is correct
8 Correct 1478 ms 95272 KB Output is correct
9 Correct 1324 ms 90324 KB Output is correct
10 Correct 1310 ms 89780 KB Output is correct
11 Correct 1715 ms 97400 KB Output is correct
12 Correct 534 ms 59976 KB Output is correct
13 Correct 1435 ms 92020 KB Output is correct
14 Correct 1306 ms 89132 KB Output is correct
15 Correct 903 ms 84852 KB Output is correct
16 Correct 938 ms 81152 KB Output is correct
17 Correct 903 ms 80444 KB Output is correct
18 Correct 973 ms 84880 KB Output is correct
19 Correct 681 ms 61924 KB Output is correct
20 Correct 345 ms 41276 KB Output is correct
21 Correct 1178 ms 84840 KB Output is correct