Submission #128062

#	Time	Username	Problem	Language	Result	Execution time	Memory
128062		BThero	Construction of Highway (JOI18_construction)	C++17	100 / 100	507 ms	86240 KiB

construction

// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;   
typedef pair<int, int> pii;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)1e5 + 5;

vector<int> adj[MAXN];

deque<pii> T[MAXN];

int group[MAXN];

int fenw[MAXN];

int boss[MAXN];

vector<pii> V;

int arr[MAXN];

int sub[MAXN];

int par[MAXN];

int h[MAXN];

pii e[MAXN];

int n, m; 

void dfs(int v, int pr = -1) {
    sub[v] = 1;

    for (int to : adj[v]) {
        if (to != pr) {
            h[to] = h[v] + 1;
            par[to] = v;
            dfs(to, v);
            sub[v] += sub[to];
        }
    }
}

void dec(int v, int pr = -1) {
    if (!boss[m]) {
        boss[m] = v;
    }

    group[v] = m;
    T[m].pb(mp(arr[v], 1));

    int mx = -1;

    for (int to : adj[v]) {
        if (to != pr) {
            if (mx == -1 || sub[to] > sub[mx]) {
                mx = to;
            }
        }
    }

    if (mx != -1) {
        dec(mx, v);
    }

    for (int to : adj[v]) {
        if (to != pr && to != mx) {
            ++m;
            dec(to, v);
        }
    }
}

void gather(int col, int cnt, int x) {
    int _cnt = cnt;
    vector<pii> V2;

    while (!T[col].empty()) {
        if (T[col].front().se > cnt) {
            V2.pb(mp(T[col].front().fi, cnt));
            T[col][0].se -= cnt;
            break;
        }
        else {
            V2.pb(T[col].front());
            cnt -= T[col].front().se;
            T[col].pop_front();
        }
    }

    while (!V2.empty()) {
        V.pb(V2.back());
        V2.pop_back();
    }

    T[col].push_front(mp(x, _cnt));
}

void fenwUpd(int p, int x) {
    for (; p <= n; p |= (p + 1)) {
        fenw[p] += x;
    }
}

int prefSum(int p) {
    int ret = 0;

    for (; p > 0; --p) {
        ret += fenw[p];
        p &= (p + 1);
    }

    return ret;
}

int query(int u, int x) {
    V.clear();

    while (u != 0) {
        int my = group[u];
        int cnt = h[u] - h[boss[my]] + 1;
        gather(my, cnt, x);
        u = par[boss[my]];
    }

    ll ans = 0;

    for (int i = 0; i < V.size(); ++i) {
        ans += prefSum(V[i].fi - 1) * 1ll * V[i].se;
        fenwUpd(V[i].fi, V[i].se);
    }

    for (int i = 0; i < V.size(); ++i) {
        fenwUpd(V[i].fi, -V[i].se);
    }

    return ans;
}

void compress() {
    vector<int> vv;

    for (int i = 1; i <= n; ++i) {
        vv.pb(arr[i]);
    }

    sort(all(vv));
    vv.resize(unique(all(vv)) - vv.begin());

    for (int i = 1; i <= n; ++i) {
        arr[i] = upper_bound(all(vv), arr[i]) - vv.begin();
    }
}

void solve() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]);
    }

    compress();

    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        e[i] = mp(u, v);
        adj[u].pb(v);
        adj[v].pb(u);
    }

    dfs(1);
    dec(1);

    for (int i = 1; i < n; ++i) {
        int u = e[i].fi, v = e[i].se;
        printf("%d\n", query(u, arr[v]));
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int query(int, int)':
construction.cpp:149:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < V.size(); ++i) {
                     ~~^~~~~~~~~~
construction.cpp:154:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < V.size(); ++i) {
                     ~~^~~~~~~~~~
construction.cpp: In function 'void solve()':
construction.cpp:177:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
construction.cpp:180:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~
construction.cpp:187:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

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