Submission #847501

#	Time	Username	Problem	Language	Result	Execution time	Memory
847501		rainboy	Closing Time (IOI23_closing)	C++17	100 / 100	192 ms	52820 KiB

closing

#include "closing.h"
#include <cstdlib>
#include <cstring>
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 200000;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

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

unsigned int X = 12345;

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

int *ej[N], *ew[N], eo[N];

void append(int i, int j, int w) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0) {
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
		ew[i] = (int *) realloc(ew[i], o * 2 * sizeof *ew[i]);
	}
	ej[i][o] = j, ew[i][o] = w;
}

int pp[N]; long long *dd; char path[N];
long long dds[N], ddt[N]; int ii[N];
long long dd1[N * 2]; int ii1[N * 2], n1;
long long dda2[N], ddb2[N]; int ii2[N], n2;
long long dp1[N * 2 + 1], dp2[N * 2 + 1];

void dfs(int p, int i, long long d) {
	pp[i] = p, dd[i] = d;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o], w = ew[i][o];
		if (j != p)
			dfs(i, j, d + w);
	}
}

int compare_ds(int i, int j) {
	return dds[i] == dds[j] ? 0 : (dds[i] < dds[j] ? -1 : 1);
}

int compare_d1(int i, int j) {
	return dd1[i] == dd1[j] ? 0 : (dd1[i] < dd1[j] ? -1 : 1);
}

int compare_db2(int i, int j) {
	return ddb2[i] == ddb2[j] ? 0 : (ddb2[i] < ddb2[j] ? -1 : 1);
}

int (*compare)(int, int);

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) {
			int c = compare(ii[j], i_);
			if (c == 0)
				j++;
			else if (c < 0) {
				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 max_score(int n, int s, int t, long long c_, vi uu, vi vv, vi ww) {
	for (int i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		ew[i] = (int *) malloc(2 * sizeof *ew[i]);
		eo[i] = 0;
	}
	for (int h = 0; h < n - 1; h++)
		append(uu[h], vv[h], ww[h]), append(vv[h], uu[h], ww[h]);
	dd = dds, dfs(-1, s, 0);
	dd = ddt, dfs(-1, t, 0);
	for (int i = 0; i < n; i++)
		if (dds[i] > ddt[i]) {
			long long tmp;
			tmp = dds[i], dds[i] = ddt[i], ddt[i] = tmp;
		}
	for (int i = 0; i < n; i++)
		ii[i] = i;
	compare = compare_ds, sort(ii, 0, n);
	int k = 0; long long c = 0;
	while (k < n && c + dds[ii[k]] <= c_)
		c += dds[ii[k++]];
	memset(path, 0, n * sizeof *path);
	for (int i = s; i != -1; i = pp[i])
		path[i] = 1;
	int k0 = 0; n1 = 0, n2 = 0;
	for (int i = 0; i < n; i++)
		if (path[i]) {
			c_ -= dds[i], k0++;
			dd1[n1++] = ddt[i] - dds[i];
		} else if (dds[i] <= ddt[i] - dds[i])
			dd1[n1++] = dds[i], dd1[n1++] = ddt[i] - dds[i];
		else
			dda2[n2] = dds[i], ddb2[n2] = ddt[i], n2++;
	if (c_ >= 0) {
		for (int i = 0; i < n1; i++)
			ii1[i] = i;
		compare = compare_d1, sort(ii1, 0, n1);
		memset(dp1, 0x3f, (n1 + 1) * sizeof *dp1), dp1[0] = 0;
		for (int i = 0; i < n1; i++)
			dp1[i + 1] = dp1[i] + dd1[ii1[i]];
		for (int i = 0; i < n2; i++)
			ii2[i] = i;
		compare = compare_db2, sort(ii2, 0, n2);
		memset(dp2, 0x3f, (n2 * 2 + 1) * sizeof *dp2), dp2[0] = 0;
		long long b = 0, d = 0;
		for (int i = 0; i < n2; i++) {
			d = max(d, ddb2[ii2[i]] - dda2[ii2[i]]), b += ddb2[ii2[i]];
			dp2[(i + 1) * 2] = b;
			dp2[(i + 1) * 2 - 1] = b - d;
		}
		long long a = INF;
		for (int i = n2 - 1; i >= 0; i--) {
			a = min(a, dda2[ii2[i]]), b -= ddb2[ii2[i]];
			dp2[i * 2 + 1] = min(dp2[i * 2 + 1], b + a);
		}
		for (int k1 = 0, k2 = n2 * 2; k1 <= n1; k1++) {
			while (k2 >= 0 && dp1[k1] + dp2[k2] > c_)
				k2--;
			if (k2 >= 0)
				k = max(k, k0 + k1 + k2);
		}
	}
	for (int i = 0; i < n; i++)
		free(ej[i]), free(ew[i]);
	return k;
}

Compilation message (stderr)

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

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 17 / 17