oj.uz

답안 #594244

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594244 2022-07-12T09:24:48 Z 반딧불(#8432) Unique Cities (JOI19_ho_t5) C++17
32 / 100
 866 ms 61228 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;
            propagate(i, l, r);
            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++){
        assert(ans[i] == 0 || ans[i] == 1);
        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);
    }
    dfsFindRootVec.pop_back();
}

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[depth[i]]++;
    }
    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 = maxTop[1], mx2 = maxTop[2];
        if(mx2.idx == i) mx2 = maxTop[2];
        if(mx1.imp <= mx2.len || mx1.imp < 1) continue;
        dfsUpdate(link[root][i], root, mx1.imp+1);
    }
}

Compilation message

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

Subtask #1
0 / 4.0

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

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 325 ms 24004 KB Output is correct
2 Correct 406 ms 37096 KB Output is correct
3 Correct 84 ms 11436 KB Output is correct
4 Correct 624 ms 40836 KB Output is correct
5 Correct 866 ms 61228 KB Output is correct
6 Correct 775 ms 50516 KB Output is correct
7 Correct 568 ms 40988 KB Output is correct
8 Correct 693 ms 42612 KB Output is correct
9 Correct 621 ms 41932 KB Output is correct
10 Correct 634 ms 41560 KB Output is correct
11 Correct 275 ms 41324 KB Output is correct
12 Correct 798 ms 53204 KB Output is correct
13 Correct 669 ms 50340 KB Output is correct
14 Correct 742 ms 49744 KB Output is correct
15 Correct 268 ms 41252 KB Output is correct
16 Correct 751 ms 54300 KB Output is correct
17 Correct 747 ms 50580 KB Output is correct

Subtask #3
0 / 32.0

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

Subtask #4
0 / 32.0

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