oj.uz

답안 #594174

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594174 2022-07-12T07:39:12 Z 이동현(#8435) Unique Cities (JOI19_ho_t5) C++17
64 / 100
 451 ms 42564 KB 
#include <bits/stdc++.h>

using namespace std;

const int NS = (int)2e5 + 4;
int n, m;
vector<int> way[NS];
int col[NS], from[NS];
int ans[NS], online[NS];
int ransval;
pair<int, int> mdis[NS];
int dis[NS];

struct fenw{
    int n;
    vector<int> tr;
    fenw(){}
    fenw(int n):n(n + 4){
        tr.resize(n);
    }
    void push(int pos, int val){
        pos += 2;
        for(int i = pos; i < n; i += (i & -i)){
            tr[i] += val;
        }
    }
    int get(int pos){
        pos += 2;
        int rv = 0;
        for(int i = pos; i > 0; i -= (i & -i)){
            rv += tr[i];
        }
        return rv;
    }
};

struct seg{
    int n;
    vector<int> cnt, sum;
    seg(){}
    void build(int x, int s, int e){
        if(s == e){
            sum[x] = 1;
            return;
        }
        int m = s + e >> 1;
        build(x * 2, s, m), build(x * 2 + 1, m + 1, e);
        sum[x] = sum[x * 2] + sum[x * 2 + 1];
    }
    seg(int n):n(n + 4){
        cnt.resize(n * 4);
        sum.resize(n * 4);
    }
    void push(int x, int s, int e, int ps, int pe, int val){
        //cout << x << ' ' << s << ' ' << e << ' ' << ps << ' ' << pe << ' ' << val << endl;
        if(pe < s || ps > e || ps > pe){
            return;
        }
        if(ps <= s && pe >= e){
            cnt[x] += val;
            if(cnt[x]) sum[x] = 0;
            else{
                if(s == e) sum[x] = 1;
                else sum[x] = sum[x * 2] + sum[x * 2 + 1];
            }
            return;
        }
        int m = s + e >> 1;
        push(x * 2, s, m, ps, pe, val), push(x * 2 + 1, m + 1, e, ps, pe, val);
        if(cnt[x]) sum[x] = 0;
        else sum[x] = sum[x * 2] + sum[x * 2 + 1];
    }
    int get(int x, int s, int e, int fs, int fe){
        //cout << x << ' ' << s << ' ' << e << ' ' << fs << ' ' << fe << endl;
        if(fe < s || fs > e || cnt[x] || fs > fe) return 0;
        if(fs <= s && fe >= e){
            return sum[x];
        }
        int m = s + e >> 1;
        return get(x * 2, s, m, fs, fe) + get(x * 2 + 1, m + 1, e, fs, fe);
    }
}tree;

pair<int, int> getfar(int x, int pr = -1){
    from[x] = pr;
    pair<int, int> rv = {0, x};
    for(auto&nxt:way[x]){
        if(nxt == pr){
            continue;
        }
        rv = max(rv, getfar(nxt, x));
    }
    return {rv.first + 1, rv.second};
}

int getdep(int x, int pr = -1){
    int rv = 0;
    for(auto&nxt:way[x]){
        if(online[nxt] || nxt == pr){
            continue;
        }
        dis[nxt] = dis[x] + 1;
        rv = max(rv, getdep(nxt, x) + 1);
        if(mdis[nxt].first > mdis[x].first) mdis[x].second = mdis[x].first, mdis[x].first = mdis[nxt].first;
        else if(mdis[nxt].first > mdis[x].second) mdis[x].second = mdis[nxt].first;
    }
    if(!mdis[x].first) mdis[x].first = dis[x];
    return rv;
}

void sol(int x, int pr = -1){
    ans[x] += ransval;
    if(mdis[x].first){
        tree.push(1, 0, n - 1, dis[x] - (mdis[x].first - dis[x]), dis[x] - 1, 1);
    }
    if(dis[x]) ans[x] += tree.get(1, 0, n - 1, 0, dis[x] - 1);
    for(auto&nxt:way[x]){
        if(online[nxt] || nxt == pr){
            continue;
        }
        if(mdis[x].first == mdis[nxt].first && mdis[x].first > mdis[x].second){
            tree.push(1, 0, n - 1, dis[x] - (mdis[x].first - dis[x]), dis[x] - 1, -1);
            if(mdis[x].second) tree.push(1, 0, n - 1, dis[x] - (mdis[x].second - dis[x]), dis[x] - 1, 1);
            sol(nxt, x);
            if(mdis[x].second) tree.push(1, 0, n - 1, dis[x] - (mdis[x].second - dis[x]), dis[x] - 1, -1);
            tree.push(1, 0, n - 1, dis[x] - (mdis[x].first - dis[x]), dis[x] - 1, 1);
        }
        else{
            sol(nxt, x);
        }
    }
    if(mdis[x].first){
        tree.push(1, 0, n - 1, dis[x] - (mdis[x].first - dis[x]), dis[x] - 1, -1);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    tree = seg(n);
    tree.build(1, 0, n - 1);
    for(int i = 1; i < n; ++i){
        int x, y; cin >> x >> y; --x, --y;
        way[x].push_back(y);
        way[y].push_back(x);
    }
    for(int i = 0; i < n; ++i){
        cin >> col[i];
    }
    int l = getfar(1).second;
    int r = getfar(l).second;
    vector<int> line;
    int now = r;
    while(true){
        line.push_back(now);
        online[now] = 1;
        if(from[now] == -1){
            break;
        }
        now = from[now];
    }
    for(int rep = 0; rep < 2; ++rep){
        for(int i = 0; i < n; ++i){
            dis[i] = 0;
            mdis[i] = {0, 0};
        }
        vector<int> dep((int)line.size()), lpos((int)line.size());
        for(int i = 0; i < (int)line.size(); ++i){
            dep[i] = getdep(line[i]);
        }
        vector<int> stk;
        for(int i = 0; i < (int)line.size(); ++i){
            while((int)stk.size() && stk.back() + dep[stk.back()] < i){
                stk.pop_back();
            }
            if((int)stk.size()){
                lpos[i] = stk.back();
            }
            while((int)stk.size() && stk.back() + dep[stk.back()] <= i + dep[i]){
                stk.pop_back();
            }
            stk.push_back(i);
        }
        int rpp = (int)line.size() - 1;
        fenw rtree((int)line.size() + 4);
        for(int i = (int)line.size() / 2 - 1 + rep * ((int)line.size() % 2); i >= 0; --i){
            while(rpp > i * 2){
                rtree.push(lpos[rpp], 1);
                --rpp;
            }
            ransval = rtree.get(i);
            sol(line[i]);
        }
        reverse(line.begin(), line.end());
    }
    for(int i = 0; i < n; ++i){
        if(col[1] == 1) ans[i] = !!ans[i];
        cout << ans[i] << '\n';
    }
    return 0;
}

Compilation message

joi2019_ho_t5.cpp: In member function 'void seg::build(int, int, int)':
joi2019_ho_t5.cpp:46:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         int m = s + e >> 1;
      |                 ~~^~~
joi2019_ho_t5.cpp: In member function 'void seg::push(int, int, int, int, int, int)':
joi2019_ho_t5.cpp:68:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int m = s + e >> 1;
      |                 ~~^~~
joi2019_ho_t5.cpp: In member function 'int seg::get(int, int, int, int, int)':
joi2019_ho_t5.cpp:79:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |         int m = s + e >> 1;
      |                 ~~^~~

Subtask #1
0 / 4.0

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

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 15628 KB Output is correct
2 Correct 131 ms 26020 KB Output is correct
3 Correct 28 ms 9124 KB Output is correct
4 Correct 368 ms 26484 KB Output is correct
5 Correct 309 ms 41680 KB Output is correct
6 Correct 400 ms 33888 KB Output is correct
7 Correct 344 ms 25888 KB Output is correct
8 Correct 451 ms 28064 KB Output is correct
9 Correct 373 ms 27580 KB Output is correct
10 Correct 331 ms 27468 KB Output is correct
11 Correct 169 ms 26412 KB Output is correct
12 Correct 296 ms 35884 KB Output is correct
13 Correct 314 ms 33784 KB Output is correct
14 Correct 376 ms 33424 KB Output is correct
15 Correct 128 ms 26176 KB Output is correct
16 Correct 245 ms 36832 KB Output is correct
17 Correct 294 ms 34192 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 19608 KB Output is correct
2 Correct 267 ms 40956 KB Output is correct
3 Correct 42 ms 9792 KB Output is correct
4 Correct 356 ms 27164 KB Output is correct
5 Correct 265 ms 42564 KB Output is correct
6 Correct 356 ms 34676 KB Output is correct
7 Correct 333 ms 26680 KB Output is correct
8 Correct 342 ms 30560 KB Output is correct
9 Correct 346 ms 29408 KB Output is correct
10 Correct 387 ms 28572 KB Output is correct
11 Correct 269 ms 26932 KB Output is correct
12 Correct 280 ms 39476 KB Output is correct
13 Correct 293 ms 33884 KB Output is correct
14 Correct 317 ms 33956 KB Output is correct
15 Correct 140 ms 27328 KB Output is correct
16 Correct 224 ms 37596 KB Output is correct
17 Correct 338 ms 34956 KB Output is correct

Subtask #4
0 / 32.0

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