Submission #241895

#	Time	Username	Problem	Language	Result	Execution time	Memory
241895		osaaateiasavtnl	Construction of Highway (JOI18_construction)	C++17	16 / 100	2078 ms	31648 KiB

construction

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 1e5+7, LG = 20;
int n, a[N], par[N];
ii d[N];
vector <int> tree[N];

int to[N][LG], h[N];
int l[N], r[N], ptr = -1;
void dfs(int u) {
    to[u][0] = par[u];
    for (int i = 1; i < LG; ++i)
        to[u][i] = to[to[u][i - 1]][i - 1];

    l[u] = ++ptr;    

    for (int v : tree[u]) {
        h[v] = h[u]+1;
        dfs(v);        
    }   

    r[u] = ptr;
}   

int mx[N << 2];
void upd(int v, int tl, int tr, int i, int x) {
    mx[v] = x;
    if (tl == tr) 
        return;
    int tm = (tl + tr) >> 1;
    if (i <= tm)
        upd(v * 2 + 1, tl, tm, i, x);
    else
        upd(v * 2 + 2, tm + 1, tr, i, x);
}
int get(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl)
        return -1;
    if (l <= tl && tr <= r)
        return mx[v];
    int tm = (tl + tr) >> 1;
    return max(get(v * 2 + 1, tl, tm, l, r), get(v * 2 + 2, tm + 1, tr, l, r));
}

int val[N];

int last(int u) {
    return get(0, 0, N, l[u], r[u]);
}

int getval(int u, int ls) {
    if (ls == -1)
        return a[u];
    else
        return val[ls];
}

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    for (int i = 0; i < (N << 2); ++i)
        mx[i] = -1;

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }   

    for (int t = 0; t < n - 1; ++t) {
        int u, v;
        cin >> u >> v;
        tree[u].app(v);
        par[v] = u;
        d[t] = mp(u,v);
    }   

    par[1] = 1;
    dfs(1);
    for (int t = 0; t < n - 1; ++t) {
        int u, v;
        tie(u, v) = d[t];

        vector <ii> path;
        while (1) {
            int up = u;
            for (int i = LG - 1; i >= 0; --i)
                if (last(to[up][i]) == last(u))
                    up = to[up][i];
            path.app(mp(getval(u, last(u)), h[u] - h[up] + 1));

            //cout << "u " << u << endl;
            //cout << "up " << up << endl;

            if (up == 1)
                break;
            else
                u = par[up];
        }   

        val[t] = a[v];
        upd(0, 0, N, l[v], t);

        /*
        cout << t << " : ";
        for (auto e : path)
            cout << e.f << ' ' << e.s << ", ";
        cout << endl;
        */

        int ans = 0;
        for (int i = 0; i < path.size(); ++i)
            for (int j = i + 1; j < path.size(); ++j)
                if (path[i].f < path[j].f)
                    ans += path[i].s * path[j].s;
        cout << ans << endl;
    }   
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:127:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < path.size(); ++i)
                         ~~^~~~~~~~~~~~~
construction.cpp:128:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = i + 1; j < path.size(); ++j)
                                 ~~^~~~~~~~~~~~~

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