oj.uz

답안 #594235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594235 2022-07-12T09:06:28 Z 반딧불(#8432) Unique Cities (JOI19_ho_t5) C++17
0 / 100
 452 ms 31892 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    int tree[800002];
    int lazy[800002];

    void propagate(int i, int l, int r){
        tree[i] += lazy[i];
        if(l!=r){
            lazy[i*2] += lazy[i];
            lazy[i*2+1] += lazy[i];
        }
        lazy[i] = 0;
    }

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

    int query(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 min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} tree;

int n, k, root;
vector<int> link[200002];
int arr[200002];
int ans[200002];

void operate();

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++) scanf("%d", &arr[i]);
    operate();
    for(int i=1; i<=n; i++) printf("%d\n", ans[i]);
}

int par[200002], depth[200002], LCADB[200002][20];
pair<int, int> maxDown[200002][3];
vector<int> dfsFindRootVec;
void dfsFindRoot(int x, int p, int goal, int loc){
    dfsFindRootVec.push_back(x);
    if(x == goal) root = dfsFindRootVec[loc];
    for(auto y: link[x]){
        if(y==p) continue;
        dfsFindRoot(y, x, goal, loc);
    }
}

void findRoot(){
    queue<int> que;
    vector<int> dist(n+2, 1e9);
    dist[1] = 0, que.push(1);
    int last = 0;
    while(!que.empty()){
        int x = last = que.front(); que.pop();
        for(auto y: link[x]){
            if(dist[y] != 1e9) continue;
            dist[y] = dist[x] + 1;
            que.push(y);
        }
    }

    dist = vector<int>(n+2, 1e9);
    dist[last] = 0, que.push(last);
    int last2 = 0;
    while(!que.empty()){
        int x = last2 = que.front(); que.pop();
        for(auto y: link[x]){
            if(dist[y] != 1e9) continue;
            dist[y] = dist[x] + 1;
            que.push(y);
        }
    }

    dfsFindRoot(last, -1, last2, dist[last2]/2);
}

void dfs(int x, int p=-1){
    maxDown[x][0] = make_pair(0, x);
    maxDown[x][1] = maxDown[x][2] = make_pair(-1e9, -1);
    for(auto y: link[x]){
        if(y==p) continue;
        par[y] = LCADB[y][0] = x, depth[y] = depth[x]+1;
        dfs(y, x);

        pair<int, int> tmp (maxDown[y][0].first+1, y);
        maxDown[x][2] = tmp;
        if(maxDown[x][1] < maxDown[x][2]) swap(maxDown[x][1], maxDown[x][2]);
        if(maxDown[x][0] < maxDown[x][1]) swap(maxDown[x][0], maxDown[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] - 2*depth[getLCA(x, y)];
}

int farBelowRoot[200002];

void dfsFar(int x, int p, int fromUp){
    farBelowRoot[x] = max(fromUp, maxDown[x][0].first);
    for(auto y: link[x]){
        if(y==p) continue;
        dfsFar(y, x, max(fromUp+1, (maxDown[x][0].second == y ? maxDown[x][1].first : maxDown[x][0].first) + 1));
    }
}

void calcRoot(){
    map<int, int> mp;
    for(int i=1; i<=n; i++){
        if(root == i) continue;
        mp[dist(i, root)]++;
    }
    for(auto x: mp) if(x.second == 1) ans[root] = 1;
}


int s;
int ancesIdx[200002];
void dfsData(int x, int p, vector<int> &v, int anc){
    v.push_back(depth[x]);
    ancesIdx[x] = anc;
    for(auto y: link[x]){
        if(y==p) continue;
        dfsData(y, x, v, anc);
    }
}

struct dat{
    int len, imp, idx;
    dat(){}
    dat(int len, int imp, int idx): len(len), imp(imp), idx(idx){}

    bool operator<(const dat &r)const{
        return len<r.len;
    }
};
dat maxTop[4];

void dfsUpdate(int x, int p, int d){
    if(farBelowRoot[x] < d) ans[x] = 1;
    for(auto y: link[x]){
        if(y==p) continue;
        dfsUpdate(y, x, d+1);
    }
}

void dfsInside(int x, int p, int d){
    if(tree.query(1, 0, n, 0, d-1-max(0, maxDown[x][0].first)) == 0) ans[x] = 1;
    for(int i=0; i<2; i++){
        if(maxDown[x][i].first >= 1){
//            printf("%d %d update: %d~%d\n", x, maxDown[x][i].second, depth[x]-maxDown[x][i].first, depth[x]-1);
            tree.update(1, 0, n, depth[x]-maxDown[x][i].first, depth[x]-1, 1);
        }
    }
    for(auto y: link[x]){
        if(y==p) continue;
        for(int i=0; i<2; i++) if(maxDown[x][i].second == y) tree.update(1, 0, n, depth[x]-maxDown[x][i].first, depth[x]-1, -1);
        dfsInside(y, x, d+1);
        for(int i=0; i<2; i++) if(maxDown[x][i].second == y) tree.update(1, 0, n, depth[x]-maxDown[x][i].first, depth[x]-1, 1);
    }
    for(int i=0; i<2; i++){
        if(maxDown[x][i].first >= 1){
            tree.update(1, 0, n, depth[x]-maxDown[x][i].first, depth[x]-1, -1);
        }
    }
}

void operate(){
    findRoot();
    dfs(root);
    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
    for(auto y: link[root]) dfsFar(y, root, 0);
    calcRoot();

    s = (int)link[root].size();
    maxTop[0] = maxTop[1] = maxTop[2] = maxTop[3] = dat(-1e9, -1e9, -1);
    for(int i=0; i<s; i++){
        int x = link[root][i];

        vector<int> v;
        dfsData(x, root, v, i);
        sort(v.begin(), v.end());
        int alone = -1;
        for(int j=0; j<(int)v.size(); j++){
            if(j+1 < (int)v.size() && v[j] == v[j+1]){
                int tmp = j;
                while(tmp+1 < (int)v.size() && v[j] == v[tmp+1]) tmp++;
                j = tmp;
                continue;
            }
            alone = max(alone, v[j]);
        }
        dat tmp (v.back(), alone, i);
        maxTop[3] = tmp;
        if(maxTop[2] < maxTop[3]) swap(maxTop[2], maxTop[3]);
        if(maxTop[1] < maxTop[2]) swap(maxTop[1], maxTop[2]);
        if(maxTop[0] < maxTop[1]) swap(maxTop[0], maxTop[1]);
    }

    for(int i=0; i<s; i++){ /// ���� ���� ���� ��
        dfsInside(link[root][i], root, 1);

        dat mx1 = maxTop[0], mx2 = maxTop[1];
        if(mx1.idx == i) mx1 = mx2, mx2 = maxTop[2];
        if(mx2.idx == i) mx2 = maxTop[2];
        if(mx1.imp <= mx2.len) continue;
        dfsUpdate(link[root][i], root, mx1.imp+1);
    }
}

Compilation message

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:57:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Incorrect 5 ms 5332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

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

Subtask #3
0 / 32.0

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

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Incorrect 5 ms 5332 KB Output isn't correct
3 Halted 0 ms 0 KB -