Submission #783194

#	Time	Username	Problem	Language	Result	Execution time	Memory
783194		Kahou	Construction of Highway (JOI18_construction)	C++14	0 / 100	2 ms	2772 KiB

construction

/* In the name of God, aka Allah */
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5 + 50, LG = 17;
int n, a[N], f[N], h[N], st[N], ft[N], par[LG][N], fen[2][N], tim;
pii P[N];
pii E[N];
vector<int> adj[N];

void dfs(int u) {
        st[u] = ++tim;
        for (int v:adj[u]) {
                h[v] = h[u]+1;
                par[0][v] = u;
                dfs(v);
        }
        ft[u] = tim;
}

int get(int c, int i) {
        int out = 0;
        for (; i > 0; i -= i&-i) out += fen[c][i];
        return out;
}
void upd(int c, int i, int x) {
        for (; i <= n; i += i&-i) fen[c][i] += x;
}

int getpar(int u) {
        int tmp = get(0, st[u]);
        int v = u;
        for (int k = LG-1; k >= 0; k--) {
                if (tmp - get(0, st[par[k][v]]) == 0) v = par[k][v];
        }
        return v;
}
void solve() {
        cin >> n;
        for (int u = 1; u <= n; u++) {
                cin >> a[u];
                P[u] = {a[u], u};
        }
        sort(P+1, P+n+1);
        int t = 0;
        for (int i = 1; i <= n; i++) {
                if (P[i].F != P[i-1].F) t++;
                a[P[i].S] = t;
        }
        for (int i = 1; i <= n-1; i++) {
                int u, v;
                cin >> u >> v;
                E[i] = {u, v};
                adj[u].push_back(v);
        }
        h[1] = 1;
        dfs(1);
        for (int k = 1; k < LG; k++) {
                for (int u = 1; u <= n; u++) {
                        par[k][u] = par[k-1][par[k-1][u]];
                }
        }
        upd(0, st[1], +1);
        upd(0, ft[1]+1, -1);
        for (int i = 1; i <= n-1; i++) {
                int u = E[i].F;
                ll out = 0;
                while (u) {
                        int v = getpar(u);
                        upd(1, a[u], h[u]-h[v]+1);
                        out += 1ll*(h[u]-h[v]+1)*get(1, a[u]-1);
                        u = par[0][v];
                }
                cout << out << endl;
                u = E[i].F;
                if (f[u]) {
                        upd(0, st[f[u]], +1);
                        upd(0, ft[f[u]]+1, -1);
                }
                f[u] = E[i].S;
                while (u) {
                        int v = getpar(u);
                        upd(1, a[u], -(h[u]-h[v]+1));
                        a[u] = a[E[i].S];
                        if (v != 1) {
                                upd(0, st[v], -1);
                                upd(0, ft[v]+1, +1);
                                upd(0, st[f[par[0][v]]], +1);
                                upd(0, ft[f[par[0][v]]]+1, -1);
                                f[par[0][v]] = v;
                        }
                        u = par[0][v];
                }
        }
}
int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}

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