Submission #1049154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049154		fryingduc	Construction of Highway (JOI18_construction)	C++17	100 / 100	1305 ms	32804 KiB

construction

#include "bits/stdc++.h"
using namespace std;

const int maxn = 1e5 + 5;
const int lg = 18;
int n, a[maxn];
vector<int> g[maxn];
int pos[maxn], cur_pos, head[maxn];
int up[maxn][lg + 1];
int sz[maxn], par[maxn];
int h[maxn];
int eu[maxn], ev[maxn];
int rev[maxn];

pair<int, int> tree[maxn * 4];
int lazy[maxn * 4];
pair<int, int> operator+(const pair<int, int> &a, const pair<int, int> &b) {
    return {max(a.first, b.first), min(a.second, b.second)};
}
struct fenwick_tree {
    #define gb(x) (x) & (-x)
    int n;
    vector<long long> bit;
    fenwick_tree() {}
    fenwick_tree(int n) : n(n), bit(n + 5, 0) {}
    void update(int x, long long val) {
        for(int i = x; i <= n; i += gb(i)) bit[i] += val;
    }
    long long get(int x) {
        int ans = 0;
        for(int i = x; i > 0; i -= gb(i)) ans += bit[i];
        
        return ans;
    }
} fen;
struct segment_tree {
    int n;
    segment_tree() {}
    segment_tree(int n) : n(n) {
        for(int i = 1; i <= n * 4; ++i) {
            tree[i] = {0, 2e9};
        }
    }
    void build(int ind, int l, int r) {
        if(l == r) {
            tree[ind] = {a[rev[l]], a[rev[l]]};
            return;
        }
        int mid = (l + r) / 2;
        build(ind * 2, l, mid);
        build(ind * 2 + 1, mid + 1, r);
        tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
    }
    void down(int ind, int l, int r) {
        tree[ind].first = tree[ind].second = lazy[ind];
        if(l != r) {
            lazy[ind * 2] = lazy[ind * 2 + 1] = lazy[ind];
        }
        lazy[ind] = 0;
    }
    void update(int ind, int l, int r, int x, int y, int val) {
        if(lazy[ind]) down(ind, l, r);
        if(l > y || r < x) return;
        if(x <= l and r <= y) {
            lazy[ind] = val;
            down(ind, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(ind * 2, l, mid, x, y, val);
        update(ind * 2 + 1, mid + 1, r, x, y, val);
        tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
    }
    pair<int, int> get(int ind, int l, int r, int x, int y) {
        if(lazy[ind]) down(ind, l, r);
        if(l > y || r < x) return {0, 2e9};
        if(x <= l and r <= y) return tree[ind];
        int mid = (l + r) / 2;
        return get(ind * 2, l, mid, x, y) + get(ind * 2 + 1, mid + 1, r, x, y);
    }
    void update(int x, int y, int val) {
        update(1, 1, n, x, y, val);
    }
    pair<int, int> get(int x, int y) {
        return get(1, 1, n, x, y);
    }
} st;
void pre_dfs(int u, int prev) {
    sz[u] = 1;
    for(auto v:g[u]) {
        if(v == prev) continue;
        par[v] = u;
        h[v] = h[u] + 1;
        up[v][0] = u;
        pre_dfs(v, u);
        sz[u] += sz[v];
    }
}
void hld(int u, int prev) {
    if(!head[u]) {
        head[u] = u;
    }
    pos[u] = ++cur_pos;
    rev[cur_pos] = u;
    int big_child = -1;
    for(auto v:g[u]) {
        if(v == prev) continue;
        if(big_child == -1 || sz[big_child] < sz[v]) big_child = v;
    }
    if(big_child != -1) {
        head[big_child] = head[u];
        hld(big_child, u);
    }
    for(auto v:g[u]) {
        if(v == prev || v == big_child) continue;
        hld(v, u);
    }
}
void update(int u, int v, int val) {
    while(head[u] != head[v]) {
        if(h[u] > h[v]) swap(u, v);
        st.update(pos[head[v]], pos[v], val);
        
        v = par[head[v]];
    }
    if(h[u] > h[v]) swap(u, v);
    st.update(pos[u], pos[v], val);
}
pair<int, int> get(int u, int v) {
    pair<int, int> ans = {0, 2e9};
    while(head[u] != head[v]) {
        if(h[u] > h[v]) swap(u, v);
        ans = ans + st.get(pos[head[v]], pos[v]);
        v = par[head[v]];
    }
    if(h[u] > h[v]) swap(u, v);
    ans = ans + st.get(pos[u], pos[v]);
    
    return ans;
}
void solve() {
    cin >> n;
    vector<int> cpr;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        cpr.push_back(a[i]);
    }
    sort(cpr.begin(), cpr.end());
    cpr.erase(unique(cpr.begin(), cpr.end()), cpr.end());
    
    for(int i = 1; i <= n; ++i)  {
        a[i] = lower_bound(cpr.begin(), cpr.end(), a[i]) - cpr.begin() + 1;
    }
    fen = fenwick_tree((int)cpr.size() + 5);
    for(int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        eu[i] = u, ev[i] = v;
        g[u].push_back(v);
//        g[v].push_back(u);
    }
    pre_dfs(1, 0);
    for(int i = 1; i <= lg; ++i) {
        for(int u = 1; u <= n; ++u) {
            up[u][i] = up[up[u][i - 1]][i - 1];
        }
    }
    hld(1, 0);
    st = segment_tree(n);
    st.build(1, 1, n);
    
    
    for(int t = 1; t < n; ++t) {
        int u = eu[t], v = ev[t];
        vector<pair<int, int>> vec;
        
        int ver = u;
        while(ver) {
            vec.push_back({st.get(pos[ver], pos[ver]).first, 1});
            for(int i = lg; i >= 0; --i) {
                if(!up[ver][i]) continue;
                int nxt = up[ver][i];
                pair<int, int> dit = get(ver, nxt);
                if(dit.first == dit.second) {
                    ver = nxt;
                    vec.back().second += (1 << i);
                }
            }
            ver = par[ver];
        }
        long long ans = 0;
        for(int i = 0; i < (int)vec.size(); ++i) {
            ans += vec[i].second * fen.get(vec[i].first - 1);
            
            fen.update(vec[i].first, vec[i].second);
        }                    
        for(auto i:vec) {
            fen.update(i.first, -i.second);
        }
        cout << ans << '\n';
        
        update(1, u, st.get(pos[v], pos[v]).first);
    }
    
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

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