Submission #967156

#	Time	Username	Problem	Language	Result	Execution time	Memory
967156		vjudge1	Construction of Highway (JOI18_construction)	C11	100 / 100	191 ms	20932 KiB

construction

#pragma GCC optimize("O3,unroll-loops")

#include <string.h>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

void reverse(int *a, int l, int r)
{
    for (int temp = --r; l < r; ++l, --r)
        temp = a[l], a[l] = a[r], a[r] = temp;
}

void sort(int *a, int l, int r)
{
    while (l < r)
    {
        int i = l, j = l, k = r, t, p = a[l + rand()%(r-l)];
        while (j < k)
        {
            if (a[j] == p) ++j;
            else if (a[j] < p) t = a[i], a[i] = a[j], a[j] = t, ++i, ++j;
            else t = a[--k], a[k] = a[j], a[j] = t;
        }
        sort(a, l, i);
        l = k;
    }
}

#define N 100000
#define M (2*N)
#define L 17

int n, c[N], tin[N], hld[N], dd[N], sz[N], par[N], c2[N];

int *eh[N], eo[N], *eh_[N], eo_[N];

long long fw[N], cost;
void fwadd(int p, long long k)
{
    for (; p < N; p |= p + 1) fw[p] += k;
}
long long fwsum(int p)
{
    long long z = 0;
    for (; p > 0; p &= p - 1) z += fw[p-1];
    return z;
}

int vv[N*L], vo;
void inversions()
{
    for (int j = 0; j < vo; j += 2)
        fwadd(vv[j+1], vv[j]),
        cost += vv[j] * fwsum(vv[j+1]);
    for (int j = 0; j < vo; j += 2)
        fwadd(vv[j+1], -vv[j]);
}

void push(int **eh, int *eo, int i, int j)
{
    int o = eo[i]++;
    if (!o) eh[i] = (int*)realloc(eh[i], 2*sizeof**eh);
    else if (!(o&o-1)) eh[i] = (int*)realloc(eh[i], 2*sizeof**eh*o);
    eh[i][o] = j;
}

void dfs1(int u, int p)
{
    par[u] = p;
    sz[u] = 1;
    for (int v, j = 0; j < eo[u]; ++j) if ((v = eh[u][j]) != p)
    {
        dd[v] = dd[u] + 1;
        dfs1(v, u);
        sz[u] += sz[v];
        if (eh[u][0] == p || sz[v] > sz[eh[u][0]])
            eh[u][j] = eh[u][0], eh[u][0] = v;
    }
}

void pushchain(int i, int j, int k)
{
    if (eo_[i] >= 2 && eh_[i][eo_[i]-2] == j)
        eh_[i][eo_[i]-1] += k;
    else
        push(eh_, eo_, i, j),
        push(eh_, eo_, i, k);
}

void dfs2(int u, int p)
{
    static int timer = 0;
    tin[u] = timer++;
    for (int v, j = 0; j < eo[u]; ++j) if ((v = eh[u][j]) != p)
        hld[v] = (j == 0) ? hld[u] : v,
        dfs2(v, u);
    pushchain(hld[u], c[u], 1);
}

int main()
{
    srand(time(0));
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", c+i);

    memcpy(c2, c, sizeof *c2 * n);
    sort(c2, 0, n);
    for (int i = 0; i < n; ++i)
    {
        int lower = -1, upper = n;
        while (upper - lower > 1)
        {
            int mid = lower + (upper - lower) / 2;
            if (c2[mid] <= c[i])
                lower = mid;
            else
                upper = mid;
        }
        c[i] = lower;
    }

    static int ee[N][2];
    for (int i = 1, u, v; i < n; ++i)
    {
        scanf("%d%d", &u, &v);
        --u, --v;
        ee[i][0] = u;
        ee[i][1] = v;
        push(eh, eo, u, v);
        push(eh, eo, v, u);
    }

    dfs1(0, -1);
    hld[0] = 0;
    dfs2(0, 0);

    for (int i = 1, u, v; i < n; ++i)
    {
        u = ee[i][0], v = ee[i][1];
        vo = 0;

        /* collect all values into vector to find inversions */
        for (int ii = u; ii != -1; ii = par[hld[ii]])
        {
            int take_here = tin[ii] - tin[hld[ii]] + 1, start = vo;
            for (int taken = 0, jj = eo_[hld[ii]] - 1; jj >= 0; jj -= 2)
            {
                int value = eh_[hld[ii]][jj-1], freq = eh_[hld[ii]][jj];
                if (freq + taken >= take_here)
                    freq = take_here - taken, jj = -1;
                if (freq)
                    vv[vo++] = value, vv[vo++] = freq;
                taken += freq;
            }
            reverse(vv, start, vo);
        }

        cost = 0;
        inversions();
        printf("%lld\n", cost);

        /* change liveliness of all node on 1-u path to liveliness[v] */
        for (int ii = u; ii != -1; ii = par[hld[ii]])
        {
            int take_here = tin[ii] - tin[hld[ii]] + 1;
            for (int taken = 0, jj = eo_[hld[ii]] - 1; jj >= 0; jj -= 2, eo_[hld[ii]] -= 2)
            {
                int freq = eh_[hld[ii]][jj];
                if (freq + taken >= take_here)
                {
                    freq = take_here - taken;
                    eh_[hld[ii]][jj] -= freq;
                    if (eh_[hld[ii]][jj] == 0)
                        eo_[hld[ii]] -= 2;
                    break;
                }
                taken += freq;
            }
            pushchain(hld[ii], c[v], take_here);
        }
    }
}

/* O(n lg^2 n)
 * proof like lct */

Compilation message (stderr)

construction.c: In function 'push':
construction.c:64:19: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   64 |     else if (!(o&o-1)) eh[i] = (int*)realloc(eh[i], 2*sizeof**eh*o);
      |                  ~^~
construction.c: In function 'main':
construction.c:104:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     scanf("%d", &n);
      |     ^~~~~~~~~~~~~~~
construction.c:106:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         scanf("%d", c+i);
      |         ^~~~~~~~~~~~~~~~
construction.c:127:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         scanf("%d%d", &u, &v);
      |         ^~~~~~~~~~~~~~~~~~~~~

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