Submission #888179

#	Time	Username	Problem	Language	Result	Execution time	Memory
888179		vjudge1	Construction of Highway (JOI18_construction)	C++17	100 / 100	813 ms	34564 KiB

construction

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv
 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);
 
 #define lid (id*2)
 #define rid (id*2+1)
 #define mid ((l+r)/2)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll L = 18;
const ll N = 1e5 + 50;
const ll Mod = 1e9 + 7;
 
ll n, c[N], par[N][L], h[N], st[N], ft[N], timer = 1, down[N];
 
vector<int> edge, adj[N];
 
void dfs(int v, int p = 0){
    par[v][0] = p;
    for(int i = 1; i < L; i++){
        if(!par[v][i-1]) break;
        par[v][i] = par[par[v][i-1]][i-1];
    }
    st[v] = timer++;
    for(int u: adj[v]){
        h[u] = h[v] + 1; dfs(u, v);
    }
    ft[v] = timer;

    down[v] = v;
}

int fen[N];

int getfen(int x){
    int out = 0;
    for(; x; x -= x & (-x)) out += fen[x];
    return out;
}

void updfen(int x, int y){
    for(; x <= n+1; x += x & (-x)) fen[x] += y;
}
 
int getPar(int v){
    int x = getfen(st[v]);
    for(int i = L-1; i >= 0; i--){
        if(x == getfen(st[par[v][i]])) v = par[v][i];
    }
    return v;
}
 
vector<int> vec;
vector<pii> block;
 
int bit[N], m;
 
void updsol(int x, int y){
    for(; x <= m; x += x & (-x)) bit[x] += y;
}
 
int getsol(int x){
    int out = 0;
    for(; x; x -= x & (-x)) out += bit[x];
    return out;
}
 
ll solve(){
    vec.clear();
    for(auto i: block) vec.pb(i.F);
 
    sort(all(vec)); vec.resize(unique(all(vec)) - vec.begin());
    m = vec.size();
 
    int sum = 0; ll res = 0;
    for(auto [x, y]: block){
        int id = lower_bound(all(vec), x) - vec.begin() + 1;
        res += 1ll * y * (sum - getsol(id)); updsol(id, y); sum += y;
    }
 
    fill(bit, bit + m+1, 0);
    return res;
}

pii seg[N*4];

void updseg(int x, pii y, int l = 1, int r = n+1, int id = 1){
    if(l+1 == r){
        seg[id] = y; return;
    }
    if(x < mid) updseg(x, y, l, mid, lid);
    else updseg(x, y, mid, r, rid);
    seg[id] = max(seg[lid], seg[rid]);
}

pii getseg(int ql, int qr, int l = 1, int r = n+1, int id = 1){
    if(ql <= l && r <= qr) return seg[id];
    if(qr <= l || r <= ql) return {0, 0};
    return max(getseg(ql, qr, l, mid, lid), getseg(ql, qr, mid, r, rid));
}
 
int main(){
    fast_io;
 
    cin >> n;
 
    for(int i = 1; i <= n; i++) cin >> c[i];
 
    int u, v; edge.pb(1);
    for(int i = 1; i < n; i++){
        cin >> u >> v;
        adj[u].pb(v); edge.pb(v);
    }
 
    dfs(1);
 
    updseg(st[1], {0, c[1]});
    updfen(st[1], 1); updfen(ft[1], -1);

    for(int i = 1; i < n; i++){
        block.clear(); 
        v = par[edge[i]][0];
        while(v){
            u = getPar(v);
            block.pb({getseg(st[v], ft[v]).S, h[v] - h[u] + 1});
            v = par[u][0];
        }
        reverse(all(block));

        cout << solve() << endl;

        v = edge[i];
        updseg(st[v], {i, c[v]});

        int last = v; v = par[v][0];
        while(v){
            u = getPar(v);
            if(down[v] != v){
                updfen(st[down[v]], 1);
                updfen(ft[down[v]], -1);
            }
            down[v] = last;

            if(u != 1){
                updfen(st[u], -1);
                updfen(ft[u], 1);
            }
            last = u;
            v = par[u][0];
        }
    }
 
}

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84