제출 #631908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631908		radal	Construction of Highway (JOI18_construction)	C++17	100 / 100	1935 ms	28064 KiB

construction

#include <bits/stdc++.h>
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define pb push_back
#define X first
#define Y second
#define debug(x) cerr << #x << " : " << x << endl;
#define all(x) x.begin() , x.end()

using namespace std;

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

constexpr int N = 1e5+10,lg = 18;

int tin[N],sz[N],seg[N*4],T,n;
int h[N],par[N][lg],c[N],fen[N];
vector<int> adj[N],ti,ci;
vector<pll> e;
void dfs(int v){
    ti.pb(v);
    tin[v] = T++;
    sz[v] = 1;
    for (int u : adj[v]){
        h[u] = h[v]+1;
        par[u][0] = v;
        dfs(u);
        sz[v] += sz[u];
    }
}

void upd(int l,int r,int p,int x,int v = 1){
    if (r-l == 1){
        seg[v] = x;
        return;
    }
    int m = (l+r) >> 1,u = (v << 1);
    if (p < m) upd(l,m,p,x,u);
    else upd(m,r,p,x,u|1);
    seg[v] = max(seg[u],seg[u|1]);
}

int que(int l,int r,int s,int e,int v = 1){
    if (l >= e || s >= r) return 0;
    if (s <= l && r <= e) return seg[v];
    int m = (l+r) >> 1,u = (v << 1);
    return max(que(l,m,s,e,u),que(m,r,s,e,u|1));
}

void upd(int r,int x){
    for (; r < n; r |= (r+1))
        fen[r] += x;
}

int que(int l){
    int ans = 0;
    for (; l >= 0; l = (l&(l+1))-1)
        ans += fen[l];
    return ans;
}
int main(){
    ios_base :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    rep(i,1,n+1){
        cin >> c[i];
        ci.pb(c[i]);
    }
    sort(all(ci));
    rep(i,1,n+1){
        c[i] = lower_bound(all(ci),c[i])-ci.begin();
    }
    e.pb({1,1});
    rep(i,1,n){
        int u,v;
        cin >> u >> v;
        e.pb({u,v});
        adj[u].pb(v);
    }
    dfs(1);
    rep(j,1,lg)
        rep(i,2,n+1)
            par[i][j] = par[par[i][j-1]][j-1];

    rep(j,1,n){
        int u = e[j].X,v = e[j].Y;
        vector<pll> ve;
        int cur = u;
        while (cur){
            int beg = cur,mx = que(0,n,tin[cur],tin[cur]+sz[cur]);
            repr(i,lg-1,0){
                if (!par[cur][i]) continue;
                int w = par[cur][i];
                if (que(0,n,tin[w],tin[w]+sz[w]) == mx) cur = w;
            }
            ve.pb({-h[cur]+h[beg]+1,c[e[mx].Y]});
            cur = par[cur][0];
        }
        ll ans = 0;
        for (auto a : ve){
            ans += 1ll*a.X*que(a.Y-1);
            upd(a.Y,a.X);
        }
        for (auto a : ve) upd(a.Y,-a.X);
        upd(0,n,tin[v],j);
        cout << ans << endl;
    }
}

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