Submission #794558

#	Time	Username	Problem	Language	Result	Execution time	Memory
794558		rainboy	Rooted MST (innopolis2021_final_E)	C11	100 / 100	545 ms	89104 KiB

Main

/* https://oj.uz/submission/418483 (gs14004) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	300000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N))) */
#define M	300000
#define W	1000000001
#define INF	0x3f3f3f3f3f3f3f3fLL

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

unsigned int X = 12345;

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

int xx[N], n;
int ii[M], jj[M], ww[M], m;

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 *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 ds[N];

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

void join(int i, int j, int w) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j, append(j, i, w);
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, append(i, j, w);
	}
}

int qu[N], ta[N], ww_[N], cnt;

void dfs(int i) {
	int o;

	qu[ta[i] = cnt++] = i;
	for (o = 0; o < eo[i]; o++) {
		int j = ej[i][o], w = ew[i][o];

		ww_[cnt] = w, dfs(j);
	}
}

long long st[N_ * 2][2][2]; int n_;

void pul(int i) {
	int l = i << 1, r = l | 1, a, b, c;

	memset(st[i], 0x3f, sizeof st[i]);
	for (a = 0; a < 2; a++)
		for (b = 0; b < 2; b++)
			for (c = 0; c < 2; c++)
				st[i][a][c] = min(st[i][a][c], st[l][a][b] + st[r][b][c]);
}

void build() {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++)
		if (i < n) {
			st[n_ + i][0][0] = ww_[i], st[n_ + i][0][1] = ww_[i] + xx[qu[i]];
			st[n_ + i][1][0] = 0, st[n_ + i][1][1] = min(ww_[i], xx[qu[i]]);
		} else {
			st[n_ + i][0][0] = 0, st[n_ + i][0][1] = INF;
			st[n_ + i][1][0] = INF, st[n_ + i][1][1] = 0;
		}
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void update(int i, int x) {
	st[n_ + i][0][0] = ww_[i], st[n_ + i][0][1] = ww_[i] + x;
	st[n_ + i][1][0] = 0, st[n_ + i][1][1] = min(ww_[i], x);
	i += n_;
	while (i > 1)
		pul(i >>= 1);
}

int main() {
	static int hh[M];
	int q, h, h_, i, x;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%d", &xx[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
		hh[h] = h;
	}
	sort(hh, 0, m);
	for (i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		ew[i] = (int *) malloc(2 * sizeof *ew[i]);
	}
	memset(ds, -1, n * sizeof *ds);
	for (h = 0; h < m; h++) {
		h_ = hh[h];
		join(ii[h_], jj[h_], ww[h_]);
	}
	for (i = 0; i < n; i++)
		join(i, i + 1, W);
	dfs(find(0));
	build();
	scanf("%d", &q);
	while (q--) {
		scanf("%d%d", &i, &x), i--;
		update(ta[i], x);
		printf("%lld\n", st[1][0][1]);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'append':
Main.c:47:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   47 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
Main.c: In function 'main':
Main.c:129:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:131:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |   scanf("%d", &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:133:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |   scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:150:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
Main.c:152:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   scanf("%d%d", &i, &x), i--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 20 / 20
• Subtask 8: 20 / 20