| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 967151 | sleepntsheep | Construction of Highway (JOI18_construction) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
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 = vo - 1; j >= 0; ----j)
{
int value = vv[j-1], freq = vv[j];
fwadd(value, freq);
cost += freq * fwsum(value);
}
for (int j = vo - 1; j >= 0; ----j)
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)
{
v = eh[u][j];
if (v == p)
continue;
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)
{
v = eh[u][j];
if (v == p)
continue;
hld[v] = (j == 0) ? hld[u] : v;
dfs2(v, u);
}
//printf(" Pushing %d to %d\n",c[u],h);
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);
{
static int c2[N];
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);
//printf(" chain[0] status : \n"); for(int j=0;j<eo_[0];j+=2) printf(" [%d %d]",eh_[0][j],eh_[0][j+1]);puts("");
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 */
//printf("collecting\n");
for (int ii = u; ii != -1; ii = par[hld[ii]])
{
int take_here = tin[ii] - tin[hld[ii]] + 1, start = vo;
//printf(" taking %d from %d\n",take_here,hld[ii]);
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);
}
reverse(vv, 0, vo);
//for (int ii=0;ii<vo;++++ii) printf(" (%d %d)\n", vv[ii],vv[ii+1]);
cost = 0;
inversions();
printf("%lld\n", cost);
/* change liveliness of all node on 1-u path to liveliness[v] */
//printf(" upding with %d\n",c[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);
}
//printf(" chain[0] status : \n"); for(int j=0;j<eo_[0];j+=2) printf(" [%d %d]",eh_[0][j],eh_[0][j+1]);puts("");puts("=========");
}
}
/* O(n lg^2 n)
* proof like lct */