Submission #645671

#	Time	Username	Problem	Language	Result	Execution time	Memory
645671		rainboy	Reconstruction Project (JOI22_reconstruction)	C11	100 / 100	1480 ms	84476 KiB

reconstruction

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

#define N	500
#define M	100000
#define Q	1000000
#define INF	0x3f3f3f3f

unsigned int X = 12345;

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

int ii[M], jj[M], ww[M], xx[Q + 1]; long long ans[Q];

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

		while (j < k) {
			if (ww[hh[j]] == ww[h])
				j++;
			else if (ww[hh[j]] < ww[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

int ds[N], uu[M], vv[M];

int find(int i) {
	return ds[i] < 0 ? i : find(ds[i]);
}

int cnt;

int join(int i, int j) {
	i = find(i);
	j = find(j);
	uu[cnt] = i, vv[cnt] = j, cnt++;
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}

void undo() {
	int i = uu[cnt - 1], j = vv[cnt - 1];

	if (ds[i] == j)
		ds[i] = -1;
	if (ds[j] == i)
		ds[j] = -1;
	cnt--;
}

long long solve_(int *hh, int m, char *used, int x) {
	int h, hl, hr, cnt_;
	long long w;

	for (h = 0; h < m; h++)
		used[hh[h]] = 0;
	hr = 0;
	while (hr < m && ww[hh[hr]] < x)
		hr++;
	hl = hr - 1, w = 0, cnt_ = cnt;
	while (hl >= 0 || hr < m) {
		int hl_ = hl < 0 ? -1 : hh[hl], hr_ = hr >= m ? -1 : hh[hr];
		int dl = hl < 0 ? INF : x - ww[hl_], dr = hr >= m ? INF : ww[hr_] - x;

		if (dl <= dr) {
			if (join(ii[hl_], jj[hl_]))
				used[hl_] = 1, w += dl;
			hl--;
		} else {
			if (join(ii[hr_], jj[hr_]))
				used[hr_] = 1, w += dr;
			hr++;
		}
	}
	while (cnt > cnt_)
		undo();
	return w;
}

char used1[M], used2[M];

void solve(int *hh, int m, int l, int r, long long a, long long b) {
	int *hh_, m_, h, h_, g, cnt_;

	if (r - l == 1) {
		ans[l] = a * xx[l] + b + solve_(hh, m, used1, xx[l]);
		return;
	}
	solve_(hh, m, used1, xx[l]), solve_(hh, m, used2, xx[r]);
	cnt_ = cnt;
	m_ = 0;
	for (h = 0; h < m; h++) {
		h_ = hh[h];
		if (xx[l] <= ww[h_] && ww[h_] <= xx[r] || used1[h_] != used2[h_])
			m_++;
		else if (used1[h_] && used2[h_]) {
			join(ii[h_], jj[h_]);
			if (ww[h_] < xx[l])
				a++, b -= ww[h_];
			else
				a--, b += ww[h_];
		}
	}
	hh_ = (int *) malloc(m_ * sizeof *hh_), m_ = 0;
	for (h = 0; h < m; h++) {
		h_ = hh[h];
		if (xx[l] <= ww[h_] && ww[h_] <= xx[r] || used1[h_] != used2[h_])
			hh_[m_++] = h_;
	}
	g = (l + r) / 2;
	solve(hh_, m_, l, g, a, b), solve(hh_, m_, g, r, a, b);
	while (cnt > cnt_)
		undo();
}

int main() {
	static int hh[M];
	int n, m, q, g, h;

	scanf("%d%d", &n, &m);
	for (h = 0; h < m; h++)
		scanf("%d%d%d", &ii[h], &jj[h], &ww[h]);
	scanf("%d", &q);
	for (g = 0; g < q; g++)
		scanf("%d", &xx[g]);
	xx[q] = INF;
	for (h = 0; h < m; h++)
		hh[h] = h;
	sort(hh, 0, m);
	memset(ds, -1, n * sizeof *ds);
	solve(hh, m, 0, q, 0, 0);
	for (g = 0; g < q; g++)
		printf("%lld\n", ans[g]);
	return 0;
}

Compilation message (stderr)

reconstruction.c: In function 'solve':
reconstruction.c:115:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  115 |   if (xx[l] <= ww[h_] && ww[h_] <= xx[r] || used1[h_] != used2[h_])
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
reconstruction.c:128:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  128 |   if (xx[l] <= ww[h_] && ww[h_] <= xx[r] || used1[h_] != used2[h_])
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
reconstruction.c: In function 'main':
reconstruction.c:141:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
reconstruction.c:143:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |   scanf("%d%d%d", &ii[h], &jj[h], &ww[h]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.c:144:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
reconstruction.c:146:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |   scanf("%d", &xx[g]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23