Submission #1194229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194229		byunjaewoo	Construction of Highway (JOI18_construction)	C++20	100 / 100	814 ms	38096 KiB

construction

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=100010, L=18, S=(1<<17);
int n, a[N], b[N], c[N];
int par[L][N], siz[N], dep[N], t, in[N], top[N], gp[N];
vector<int> com;
vector<int> adj[N];

class LazyProp {
public:
    void update(int l, int r, int v) {update(1, 1, S, l, r, v);}
    int query(int k) {return query(1, 1, S, k);}
private:
    int tree[2*S], lazy[2*S];
    void propagate(int node, int s, int e) {
        if (!lazy[node]) return;
        if (s!=e) lazy[2*node]=lazy[2*node+1]=lazy[node];
        else tree[node]=lazy[node];
        lazy[node]=0;
    }
    void update(int node, int s, int e, int l, int r, int v) {
        propagate(node, s, e);
        if (s>r || l>e) return;
        if (l<=s && e<=r) {
            lazy[node]=v, propagate(node, s, e);
            return;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        update(lch, s, m, l, r, v), update(rch, m+1, e, l, r, v);
    }
    int query(int node, int s, int e, int k) {
        propagate(node, s, e);
        if (s==e) return tree[node];
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if (k<=m) return query(lch, s, m, k);
        return query(rch, m+1, e, k);
    }
}T;

class Fenwick {
public:
    void update(int k, int v) {
        for (int i=k; i<=n; i+=i&-i) tree[i]+=v;
    }
    int query(int k) {
        int ret=0;
        for (int i=k; i>=1; i-=i&-i) ret+=tree[i];
        return ret;
    }
private:
    int tree[N];
}T2;

void dfs(int curr) {
    for (int i=1; i<L; i++) par[i][curr]=par[i-1][par[i-1][curr]];
    siz[curr]=1;
    for (int next:adj[curr]) {
        par[0][next]=curr, dep[next]=dep[curr]+1, dfs(next), siz[curr]+=siz[next];
    }
    for (int &next:adj[curr]) if (siz[next]>siz[adj[curr][0]]) swap(next, adj[curr][0]);
}

void dfs2(int curr) {
    in[curr]=++t;
    for (int next:adj[curr]) {
        if (next==adj[curr][0]) top[next]=top[curr];
        else top[next]=next;
        dfs2(next);
    }
}

int lift(int x, int y) {
    for (int i=L-1; i>=0; i--) if (par[i][x] && dep[par[i][x]]>dep[y]) x=par[i][x];
    return x;
}

int query(int x) {
    vector<array<int, 2>> vec;
    while (x) {
        int tmp=T.query(in[x]);
        vec.push_back({c[tmp], dep[x]-dep[gp[tmp]]+1});
        int ttmp=par[0][gp[tmp]];
        gp[tmp]=lift(tmp, x);
        x=ttmp;
    }
    int ret=0;
    for (int i=0; i<vec.size(); i++) {
        ret+=T2.query(vec[i][0]-1)*vec[i][1], T2.update(vec[i][0], vec[i][1]);
    }
    for (int i=0; i<vec.size(); i++) T2.update(vec[i][0], -vec[i][1]);
    return ret;
}

void update(int x, int v) {
    gp[v]=1;
    while (x) T.update(in[top[x]], in[x], v), x=par[0][top[x]];
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>c[i], com.push_back(c[i]);
    sort(com.begin(), com.end()), com.erase(unique(com.begin(), com.end()), com.end());
    for (int i=1; i<=n; i++) c[i]=lower_bound(com.begin(), com.end(), c[i])-com.begin()+1;
    for (int i=1; i<n; i++) {
        cin>>a[i]>>b[i];
        adj[a[i]].push_back(b[i]);
    }
    dfs(1), dfs2(1);
    for (int i=1; i<=n; i++) T.update(in[i], in[i], i), gp[i]=i;
    for (int i=1; i<n; i++) {
        cout<<query(a[i])<<"\n";
        update(a[i], b[i]);
    }
    return 0;
}

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