oj.uz

답안 #263518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
263518 2020-08-13T18:31:01 Z doowey Construction of Highway (JOI18_construction) C++14
0 / 100
 4 ms 5120 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;

int A[N], B[N], C[N];
vector<int> T[N];
int subt[N];
int dep[N];
int link[N];
int par[N];

void dfs(int u){
    subt[u]=1;
    for(auto x : T[u]){
        dep[x]=dep[u]+1;
        par[x]=u;
        dfs(x);
        subt[u]+=subt[x];
    }
}

void hld(int u){
    for(auto x : T[u]){
        if(subt[x] > (subt[u] + 1) / 2){
            link[x]=link[u];
        }
        else{
            link[x]=x;
        }
        hld(x);
    }
}

vector<pii> vals[N];

vector<int> ups;

int lim;
int tree[N * 2];

void upd(int id, int v){
    id += lim;
    while(id > 0){
        tree[id] += v;
        ups.push_back(id);
        id /= 2;
    }
}

int get(int l, int r){
    int cnt = 0;
    l += lim;
    r += lim;
    while(l <= r){
        if(l % 2 == 1) cnt += tree[l ++];
        if(r % 2 == 0) cnt += tree[r --];
        l /= 2;
        r /= 2;
    }
    return cnt;
}

ll setv(int node, int bb){
    ll ret = 0;
    int en;
    int len;
    int cur;
    int low;
    vector<pii> lines;
    vector<pii> curs;
    while(1){
        en = link[node];
        len = dep[node]-dep[en]+1;
        cur = len;
        curs.clear();
        while(cur > 0){
            low = min(cur, vals[en].back().fi);
            curs.push_back(mp(low, vals[en].back().se));
            vals[en].back().fi -= low;
            cur -= low;
            if(vals[en].back().fi == 0)
                vals[en].pop_back();
        }
        reverse(curs.begin(), curs.end());
        for(auto x : curs)
            lines.push_back(x);
        vals[en].push_back(mp(len, bb));
        if(en == 1) break;
        node = par[en];
    }
    reverse(lines.begin(), lines.end());
    ups.clear();
    for(auto pq : lines){
        ret += get(pq.se + 1, lim - 1);
        upd(pq.se, pq.fi);
    }
    for(auto x : ups){
        tree[x]=0;
    }
    return ret;
}

int main(){
    fastIO;
    int n;
    cin >> n;
    vector<int> x;
    for(int i = 1; i <= n; i ++ ){
        cin >> C[i];
        x.push_back(C[i]);
    }
    sort(x.begin(), x.end());
    x.resize(unique(x.begin(), x.end()) - x.begin());
    lim = x.size();
    for(int i = 1; i <= n; i ++ ){
        C[i] = lower_bound(x.begin(), x.end(), C[i]) - x.begin();
    }
    int u, v;
    for(int i = 1; i < n; i ++ ){
        cin >> A[i] >> B[i];
        T[A[i]].push_back(B[i]);
    }
    link[1]=1;
    dfs(1);
    hld(1);
    par[1]=1;
    vals[1].push_back(mp(1, 1));
    for(int i = 1; i < n; i ++ ){
        cout << setv(A[i], C[B[i]]) << "\n";
        if(vals[link[B[i]]].empty() || vals[link[B[i]]].back().se != C[B[i]]){
            vals[link[B[i]]].push_back(mp(1, C[B[i]]));
        }
        else{
            vals[link[B[i]]].back().fi ++ ;
        }
    }
    return 0;
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:128:9: warning: unused variable 'u' [-Wunused-variable]
  128 |     int u, v;
      |         ^
construction.cpp:128:12: warning: unused variable 'v' [-Wunused-variable]
  128 |     int u, v;
      |            ^

Subtask #1
0 / 7.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 84.0

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