oj.uz

Submission #793483

# Submission time Handle Problem Language Result Execution time Memory
793483 2023-07-25T22:32:05 Z rainboy Rooted MST (innopolis2021_final_E) C
60 / 100
 4000 ms 83732 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define N	300000
#define M	600000
#define Q	300000
#define K	(N + Q)
#define N_	(1 << 20)	/* N_ = pow2(ceil(log2(N * 2))) */
#define INF	0x3f3f3f3f
 
int max(int a, int b) { return a > b ? a : b; }
 
unsigned int X = 12345;
 
int rand_() {
	return (X *= 3) >> 1;
}
 
int ii[M], jj[M], ww[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) {
			int c = ww[hh[j]] != ww[h] ? ww[hh[j]] - ww[h] : hh[j] - h;

			if (c == 0)
				j++;
			else if (c < 0) {
				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], eo[N];
 
void append(int i, int j) {
	int o = eo[i]++;
 
	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}
 
int ta[N], tb[N], qu[N * 2];
 
void dfs(int p, int i) {
	static int time;
	int o;
 
	qu[ta[i] = time++] = i;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];
 
		if (j != p)
			dfs(i, j);
	}
	qu[tb[i] = time++] = i;
}
 
int sum[N_ * 2], suf[N_ * 2], n_;
 
void pul(int i) {
	int l = i << 1, r = l | 1;
 
	sum[i] = sum[l] + sum[r], suf[i] = max(suf[l] + sum[r], suf[r]);
}
 
void update(int i, int x) {
	i += n_;
	suf[i] = max(sum[i] += x, 0);
	while (i > 1)
		pul(i >>= 1);
}
 
int prev(int r) {
	int l = 0, s = 0;
 
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0) {
			if (s + suf[r] > 0) {
				while (r < n_)
					if (s + suf[r << 1 | 1] > 0)
						r = r << 1 | 1;
					else
						s += sum[r << 1 | 1], r = r << 1 | 0;
				return r - n_;
			}
			s += sum[r--];
		}
	return -1;
}
 
int ds[N], hh_[N];
 
int find(int i) {
	return ds[i] < 0 ? i : find(ds[i]);
}
 
long long ans;
 
void join(int h) {
	int i = find(ii[h]), j = find(jj[h]);
 
	if (i == j)
		return;
	append(ii[h], jj[h]), append(jj[h], ii[h]), ans += ww[h];
	if (ds[i] > ds[j])
		ds[i] = j, hh_[i] = h;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, hh_[j] = h;
	}
}
 
int query(int i, int j) {
	int h = -1;
 
	while (i != j)
		if (hh_[j] == -1 || hh_[i] != -1 && ww[hh_[i]] < ww[hh_[j]] || ww[hh_[i]] == ww[hh_[j]] && hh_[i] < hh_[j])
			h = hh_[i], i = ds[i];
		else
			h = hh_[j], j = ds[j];
	return h;
}
 
int xx[N], uu[N], tt[N], zz[N], dd[N], cnt;
 
void add(int i, int x) {
	int r, u, h, j;
 
	xx[i] = x;
	r = qu[prev(ta[i])];
	if (uu[r] == -1) {
		ans += x, tt[cnt] = -1, dd[cnt] = x, cnt++;
		uu[r] = i;
	} else {
		u = uu[r], h = query(u, i);
		if (max(ww[h], xx[u]) <= x)
			tt[cnt] = 0, dd[cnt] = 0, cnt++;
		else if (ww[h] < xx[u]) {
			ans += x - xx[u], tt[cnt] = 1, zz[cnt] = u, dd[cnt] = x - xx[u], cnt++;
			uu[r] = i;
		} else {
			ans += x - ww[h], tt[cnt] = 2, zz[cnt] = h, dd[cnt] = x - ww[h], cnt++;
			j = ta[ii[h]] > ta[jj[h]] ? ii[h] : jj[h];
			update(ta[j], 1), update(tb[j], -1);
			if (ta[j] <= ta[i] && ta[i] <= tb[j])
				uu[j] = i;
			else
				uu[r] = i, uu[j] = u;
		}
	}
}
 
void undo(int i) {
	int r, h, j;
 
	cnt--;
	ans -= dd[cnt];
	r = qu[prev(ta[i])];
	if (tt[cnt] == -1)
		uu[r] = -1;
	else if (tt[cnt] == 1)
		uu[r] = zz[cnt];
	else if (tt[cnt] == 2) {
		h = zz[cnt], j = ta[ii[h]] > ta[jj[h]] ? ii[h] : jj[h];
		if (ta[i] < ta[j] || ta[i] > tb[j])
			uu[r] = uu[j];
		update(ta[j], -1), update(tb[j], 1);
	}
}
 
int ll[K], rr[K], ii_[K], xx_[K], k;
 
void solve(int *gg, int k, int l, int r) {
	int g, g_, g1, g2, g3, m, tmp;
 
	g1 = 0, g2 = 0, g3 = k;
	while (g2 < g3)
		if (ll[gg[g2]] <= l && r <= rr[gg[g2]])
			g2++;
		else if (ll[gg[g2]] < r && l < rr[gg[g2]]) {
			tmp = gg[g1], gg[g1] = gg[g2], gg[g2] = tmp;
			g1++, g2++;
		} else {
			g3--;
			tmp = gg[g2], gg[g2] = gg[g3], gg[g3] = tmp;
		}
	for (g = g1; g < g2; g++) {
		g_ = gg[g];
		add(ii_[g_], xx_[g_]);
	}
	if (r - l == 1)
		printf("%lld\n", ans);
	else {
		m = (l + r) / 2;
		solve(gg, g1, l, m), solve(gg, g1, m, r);
	}
	for (g = g2 - 1; g >= g1; g--) {
		g_ = gg[g];
		undo(ii_[g_]);
	}
}
 
int main() {
	static int tt[N], hh[M], gg[K];
	int n, m, q, g, h, i, t, 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]--;
	for (i = 0; i + 1 < n; i++)
		ii[m] = i, jj[m] = i + 1, ww[m] = INF, m++;
	for (h = 0; h < m; h++)
		hh[h] = h;
	sort(hh, 0, m);
	memset(ds, -1, n * sizeof *ds), memset(hh_, -1, n * sizeof *hh_);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < m; h++)
		join(hh[h]);
	dfs(-1, 0);
	scanf("%d", &q);
	for (t = 0; t < q; t++) {
		scanf("%d%d", &i, &x), i--;
		if (tt[i] < t)
			ll[k] = tt[i], rr[k] = t, ii_[k] = i, xx_[k] = xx[i], k++;
		xx[i] = x, tt[i] = t;
	}
	for (i = 0; i < n; i++)
		ll[k] = tt[i], rr[k] = q, ii_[k] = i, xx_[k] = xx[i], k++;
	for (g = 0; g < k; g++)
		gg[g] = g;
	n_ = 1;
	while (n_ < n * 2)
		n_ <<= 1;
	update(ta[0], 1), update(tb[0], -1);
	uu[0] = -1;
	solve(gg, k, 0, q);
	return 0;
}

Compilation message

Main.c: In function 'append':
Main.c:49:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   49 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'query':
Main.c:130:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  130 |   if (hh_[j] == -1 || hh_[i] != -1 && ww[hh_[i]] < ww[hh_[j]] || ww[hh_[i]] == ww[hh_[j]] && hh_[i] < hh_[j])
      |                       ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:130:91: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  130 |   if (hh_[j] == -1 || hh_[i] != -1 && ww[hh_[i]] < ww[hh_[j]] || ww[hh_[i]] == ww[hh_[j]] && hh_[i] < hh_[j])
      |                                                                  ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
Main.c: In function 'main':
Main.c:220:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:222:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  222 |   scanf("%d", &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:224:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |   scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:236:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  236 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
Main.c:238:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |   scanf("%d%d", &i, &x), i--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 7 ms 964 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3680 ms 60548 KB Output is correct
2 Correct 3815 ms 63272 KB Output is correct
3 Correct 625 ms 17176 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 975 ms 12736 KB Output is correct
2 Correct 936 ms 11020 KB Output is correct
3 Correct 870 ms 8776 KB Output is correct
4 Execution timed out 4103 ms 63480 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 58044 KB Output is correct
2 Correct 727 ms 64048 KB Output is correct
3 Correct 615 ms 64032 KB Output is correct
4 Correct 199 ms 23128 KB Output is correct
5 Correct 163 ms 19744 KB Output is correct
6 Correct 113 ms 15144 KB Output is correct
7 Correct 709 ms 72632 KB Output is correct
8 Correct 669 ms 72512 KB Output is correct
9 Correct 1034 ms 72476 KB Output is correct
10 Correct 1014 ms 72676 KB Output is correct
11 Correct 1014 ms 72832 KB Output is correct
12 Correct 738 ms 73504 KB Output is correct
13 Correct 668 ms 73932 KB Output is correct
14 Correct 605 ms 74848 KB Output is correct
15 Correct 568 ms 74828 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 58044 KB Output is correct
2 Correct 727 ms 64048 KB Output is correct
3 Correct 615 ms 64032 KB Output is correct
4 Correct 199 ms 23128 KB Output is correct
5 Correct 163 ms 19744 KB Output is correct
6 Correct 113 ms 15144 KB Output is correct
7 Correct 709 ms 72632 KB Output is correct
8 Correct 669 ms 72512 KB Output is correct
9 Correct 1034 ms 72476 KB Output is correct
10 Correct 1014 ms 72676 KB Output is correct
11 Correct 1014 ms 72832 KB Output is correct
12 Correct 738 ms 73504 KB Output is correct
13 Correct 668 ms 73932 KB Output is correct
14 Correct 605 ms 74848 KB Output is correct
15 Correct 568 ms 74828 KB Output is correct
16 Correct 1272 ms 64412 KB Output is correct
17 Correct 1261 ms 63900 KB Output is correct
18 Correct 1129 ms 63976 KB Output is correct
19 Correct 259 ms 23028 KB Output is correct
20 Correct 234 ms 19792 KB Output is correct
21 Correct 172 ms 15180 KB Output is correct
22 Correct 989 ms 72568 KB Output is correct
23 Correct 991 ms 72520 KB Output is correct
24 Correct 907 ms 72452 KB Output is correct
25 Correct 691 ms 72532 KB Output is correct
26 Correct 713 ms 72832 KB Output is correct
27 Correct 717 ms 73408 KB Output is correct
28 Correct 932 ms 73952 KB Output is correct
29 Correct 829 ms 74720 KB Output is correct
30 Correct 817 ms 74788 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3840 ms 82392 KB Output is correct
2 Correct 3864 ms 82480 KB Output is correct
3 Correct 3844 ms 83016 KB Output is correct
4 Correct 3744 ms 83732 KB Output is correct
5 Correct 3978 ms 81172 KB Output is correct
6 Execution timed out 4054 ms 80988 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 7 ms 964 KB Output is correct
6 Correct 1564 ms 33632 KB Output is correct
7 Correct 1592 ms 33272 KB Output is correct
8 Correct 1536 ms 33520 KB Output is correct
9 Correct 1432 ms 38756 KB Output is correct
10 Correct 340 ms 12152 KB Output is correct
11 Correct 311 ms 10444 KB Output is correct
12 Correct 309 ms 9108 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 7 ms 964 KB Output is correct
6 Correct 3680 ms 60548 KB Output is correct
7 Correct 3815 ms 63272 KB Output is correct
8 Correct 625 ms 17176 KB Output is correct
9 Correct 975 ms 12736 KB Output is correct
10 Correct 936 ms 11020 KB Output is correct
11 Correct 870 ms 8776 KB Output is correct
12 Execution timed out 4103 ms 63480 KB Time limit exceeded
13 Halted 0 ms 0 KB -