Submission #517326

#	Time	Username	Problem	Language	Result	Execution time	Memory
517326		couplefire	Construction of Highway (JOI18_construction)	C++17	100 / 100	1126 ms	129992 KiB

construction

#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);
    }
}
 
deque<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) * 1ll * pq.fi;
        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, C[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]]].front().se != C[B[i]]){
            vals[link[B[i]]].push_front(mp(1, C[B[i]]));
        }
        else{
            vals[link[B[i]]].front().fi ++ ;
        }
    }
    return 0;
}

Compilation message (stderr)

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: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84