oj.uz

답안 #412101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
412101 2021-05-26T13:56:43 Z 반딧불(#7584) Pastiri (COI20_pastiri) C++17
8 / 100
 760 ms 134124 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;

struct segTree{
    int tree[2000002], lazy[2000002]; /// a a+2 a+4 ... ���·� ������ ���̴�.

    void init(int i, int l, int r){
        tree[i] = lazy[i] = -1e9;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m), init(i*2+1, m+1, r);
    }

    void propagate(int i, int l, int r){
        tree[i] = max(tree[i], lazy[i] + 2*(r-l));
        if(l!=r){
            int m = (l+r)>>1;
            lazy[i*2] = max(lazy[i*2], lazy[i]);
            lazy[i*2+1] = max(lazy[i*2+1], lazy[i] + 2*(m+1-l));
        }
        lazy[i] = -1e9;
    }

    void update(int i, int l, int r, int s, int e, int x){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] = max(lazy[i], x);
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, x);
        update(i*2+1, m+1, r, s, e, x + 2*(m+1-l));
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    int getVal(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return -1e9;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(getVal(i*2, l, m, s, e), getVal(i*2+1, m+1, r, s, e));
    }
} sgtree;

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], top[500002], inCnt;
vector<int> loc;
int ans;
int ansX[500002], ansY[500002];

void dfs_first(int x, int p=-1){
    if(p != -1) link[x].erase(find(link[x].begin(), link[x].end(), p));
    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];

        if(sz[link[x][0]] < sz[y]) swap(link[x][0], y);
    }
}

void dfs_second(int x, int p=-1, int fromUp=1e9){
    minDist[x] = min(minDist[x], fromUp);
    in[x] = ++inCnt;
    idx[in[x]] = x;
    for(auto y: link[x]){
        if(y == p) continue;
        if(link[x][0] == y) top[y] = top[x];
        else top[y] = y;
        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;
}

bool already(int x){
    if(tree.get(in[x])) return true;
    int tDepth = depth[x];
    while(x){
        if(tDepth <= sgtree.getVal(1, 1, n, in[top[x]], in[x])) return true;
        x = par[top[x]];
    }
    return false;
}

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);
    top[1] = 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;
    sgtree.init(1, 1, 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(already(p)) continue;

        int targ = p, cnt = 0;
        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, cnt += (1<<d);
        }

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

        int fDepth = depth[targ];
        while(targ){
            int tp = top[targ];
            if(depth[targ] < fDepth-cnt) break;
            sgtree.update(1, 1, n, in[tp], in[targ], 2 * depth[tp] + cnt - fDepth);
            targ = par[tp];
        }
    }

    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:129:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
pastiri.cpp:132:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
pastiri.cpp:138:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 345 ms 128416 KB Output is correct
2 Correct 377 ms 130120 KB Output is correct
3 Correct 339 ms 130192 KB Output is correct
4 Correct 687 ms 134124 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 13004 KB Sheep 4257 not protected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 12380 KB Sheep 12 not protected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 760 ms 92064 KB Sheep 54 not protected
2 Halted 0 ms 0 KB -