oj.uz

Submission #412076

# Submission time Handle Problem Language Result Execution time Memory
412076 2021-05-26T13:29:19 Z 반딧불(#7584) Pastiri (COI20_pastiri) C++17
0 / 100
 734 ms 119652 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Fenwick{
    int n;
    int tree[500002];

    void add(int x, int y){
        while(x){
            tree[x] += y;
            x -= x&-x;
        }
    }
    int get(int x){
        int ret = 0;
        while(x<=n){
            ret += tree[x];
            x += x&-x;
        }
        return ret;
    }
} tree;

int n, k;
int par[500002], LCADB[500002][20];
vector<int> link[500002];
int minDist[500002], depth[500002];
int in[500002], idx[500002], sz[500002], inCnt;
vector<int> loc;

int ans;
int ansX[500002], ansY[500002];

void dfs_first(int x, int p=-1){
    in[x] = ++inCnt;
    idx[in[x]] = x;
    sz[x] = 1;
    for(auto y: link[x]){
        if(y == p) continue;
        par[y] = x;
        depth[y] = depth[x]+1;
        dfs_first(y, x);
        minDist[x] = min(minDist[x], minDist[y]+1);
        sz[x] += sz[y];
    }
}

void dfs_second(int x, int p=-1, int fromUp=1e9){
    minDist[x] = min(minDist[x], fromUp);
    for(auto y: link[x]){
        if(y == p) continue;
        dfs_second(y, x, minDist[x]+1);
    }
}

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

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

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y), link[y].push_back(x);
    }
    for(int i=1; i<=n; i++) minDist[i] = 1e9;
    for(int i=1; i<=k; i++){
        int x;
        scanf("%d", &x);
        minDist[x] = 0;
        loc.push_back(x);
    }
    dfs_first(1);
    dfs_second(1);
    for(int i=1; i<=n; i++) LCADB[i][0] = par[i];
    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];

    tree.n = n;
    sort(loc.begin(), loc.end(), [&](int x, int y){
        return depth[x] > depth[y];
    });
    for(int i=0; i<k; i++){
        int p = loc[i];
        if(tree.get(in[p])) continue;

        int targ = p;
        for(int d=19; d>=0; d--){
            if(LCADB[targ][d] == 0) continue;
            int p2 = LCADB[targ][d];
            if(depth[p] - depth[p2] == minDist[p2]) targ = p2;
        }

        tree.add(in[targ] + sz[targ] - 1, 1);
        tree.add(in[targ] - 1, -1);
        ansX[ans] = targ;
        ans++;
    }

    printf("%d\n", ans);
    for(int i=0; i<ans; i++) printf("%d ", ansX[i]);
}

Compilation message

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 117700 KB Output is correct
2 Incorrect 331 ms 119652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 12748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 734 ms 81592 KB Output isn't correct
2 Halted 0 ms 0 KB -