Submission #466579

#	Time	Username	Problem	Language	Result	Execution time	Memory
466579		rainboy	Road Closures (APIO21_roads)	C++17	100 / 100	171 ms	39880 KiB

roads

#include "roads.h"
#include <stdlib.h>
#include <vector>

using namespace std;

typedef vector<int> vi;
typedef vector<long long> vl;

long long max(long long a, long long b) { return a > b ? a : b; }

const int N = 100000;

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

long long *zz;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (zz[ii[j]] == zz[i_])
				j++;
			else if (zz[ii[j]] < zz[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int uu[N - 1], vv[N - 1]; long long ww[N - 1]; int idx[N - 1][2];

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

void append(int **eh, int *eo, int i, int h) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

long long *st[N]; int *kk_[N], nn_[N];

void build(int u, int n) {
	int n_;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	nn_[u] = n_;
	st[u] = (long long *) calloc(n_ * 2, sizeof *st[u]), kk_[u] = (int *) calloc(n_ * 2, sizeof *kk_[u]);
}

void pul(int u, int i) {
	int l = i << 1, r = l | 1;

	st[u][i] = st[u][l] + st[u][r], kk_[u][i] = kk_[u][l] + kk_[u][r];
}

void update(int u, int i, int x, int k) {
	int n_ = nn_[u];

	i += n_;
	st[u][i] += x, kk_[u][i] += k;
	while (i > 1)
		pul(u, i >>= 1);
}

long long query(int u, int k) {
	int n_ = nn_[u], i;
	long long sum;

	i = 1, sum = 0;
	while (i < n_)
		if (k < kk_[u][i << 1 | 0])
			i = i << 1 | 0;
		else
			sum += st[u][i << 1 | 0], k -= kk_[u][i << 1 | 0], i = i << 1 | 1;
	if (k >= kk_[u][i])
		sum += st[u][i], k -= kk_[u][i];
	return sum;
}

long long aa[N], dp[N], dq[N]; int ii_[N], k_;
char visited[N], marked[N];

void dfs(int p, int i) {
	int o, n_, i_, k;
	long long x;

	visited[i] = 1;
	x = 0;
	for (o = eo_[i]; o--; ) {
		int h = eh_[i][o], j = i ^ uu[h] ^ vv[h];
		
		if (j != p) {
			dfs(i, j);
			x += dp[j];
		}
	}
	n_ = 0;
	for (o = eo_[i]; o--; ) {
		int h = eh_[i][o], j = i ^ uu[h] ^ vv[h];
		
		if (j != p)
			aa[n_++] = dq[j] + ww[h] - dp[j];
	}
	for (i_ = 0; i_ < n_; i_++)
		ii_[i_] = i_;
	zz = aa, sort(ii_, 0, n_);
	dp[i] = 0, dq[i] = 0;
	for (k = 0; k <= k_ && k <= n_; k++) {
		dp[i] = max(dp[i], x + query(i, k_ - k));
		if (k < k_)
			dq[i] = max(dq[i], x + query(i, k_ - 1 - k));
		if (k < n_)
			x += aa[ii_[n_ - 1 - k]];
	}
}

int ii[N], cnt[N];

vl minimum_closure_costs(int n, vi uu_, vi vv_, vi ww_) {
	vl ans(n);
	int g, g_, h, i, j, k, o;
	long long sum;

	for (h = 0; h < n - 1; h++)
		uu[h] = uu_[h], vv[h] = vv_[h], ww[h] = ww_[h];
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < n - 1; h++)
		append(eh, eo, uu[h], h), append(eh, eo, vv[h], h);
	for (i = 0; i < n; i++)
		cnt[eo[i]]++;
	for (k = 1; k < n; k++)
		cnt[k] += cnt[k - 1];
	for (i = 0; i < n; i++)
		ii[cnt[eo[i] - 1]++] = i;
	for (h = 0; h < n - 1; h++)
		ans[0] += ww[h];
	for (i = 0; i < n; i++) {
		zz = ww, sort(eh[i], 0, eo[i]);
		for (o = 0; o < eo[i]; o++) {
			h = eh[i][o];
			idx[h][uu[h] == i ? 0 : 1] = eo[i] - 1 - o;
		}
		build(i, eo[i]);
	}
	for (i = 0; i < n; i++)
		eh_[i] = (int *) malloc(2 * sizeof *eh_[i]);
	sum = ans[0];
	for (k_ = n - 1, g = n - 1; k_ > 0; k_--) {
		while (g >= 0 && eo[ii[g]] > k_) {
			i = ii[g--];
			marked[i] = 1;
			for (o = eo[i]; o--; ) {
				h = eh[i][o], j = i ^ uu[h] ^ vv[h];
				if (!marked[j])
					update(i, idx[h][uu[h] == i ? 0 : 1], ww[h], 1), sum -= ww[h];
				else {
					update(j, idx[h][uu[h] == j ? 0 : 1], -ww[h], -1);
					append(eh_, eo_, i, h), append(eh_, eo_, j, h);
				}
			}
		}
		for (g_ = g + 1; g_ < n; g_++)
			visited[ii[g_]] = 0;
		ans[k_] = ans[0] - sum;
		for (g_ = g + 1; g_ < n; g_++) {
			i = ii[g_];
			if (!visited[i]) {
				dfs(-1, i);
				ans[k_] -= dp[i];
			}
		}
	}
	return ans;
}

Compilation message (stderr)

roads.cpp: In function 'void append(int**, int*, int, int)':
roads.cpp:48:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   48 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22