oj.uz

Submission #412077

# Submission time Handle Problem Language Result Execution time Memory
412077 2021-05-26T13:30:30 Z 반딧불(#7584) Pastiri (COI20_pastiri) C++17
8 / 100
 699 ms 122456 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];

    sort(loc.begin(), loc.end());
    vector<int> ansV;
    for(int i=0; i<k; i++){
        if(i<k-1 && (loc[i] + loc[i+1]) % 2 == 0){
            ansV.push_back((loc[i] + loc[i+1]) / 2);
            i++;
        }
        else ansV.push_back(loc[i]);
    }
    printf("%d\n", (int)ansV.size());
    for(auto x: ansV) printf("%d ", x);
}

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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 117828 KB Output is correct
2 Correct 323 ms 117676 KB Output is correct
3 Correct 321 ms 117708 KB Output is correct
4 Correct 454 ms 122456 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 12776 KB Sheep 3030 not protected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 12364 KB Sheep 128 not protected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 699 ms 79632 KB Sheep 54 not protected
2 Halted 0 ms 0 KB -