제출 #788125

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
788125		rainboy	Grapevine (NOI22_grapevine)	C11	100 / 100	790 ms	106768 KiB

Main

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

#define N	100000
#define K	16	/* K = floor(log2(N)) */
#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 n;

int ii[N - 1], jj[N - 1], ww[N - 1], hh[N - 1];

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 = ii[hh[j]] != ii[h] ? ii[hh[j]] - ii[h] : jj[hh[j]] - jj[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 search(int i, int j) {
	int lower = -1, upper = n - 1;

	while (upper - lower > 1) {
		int h = (lower + upper) / 2;

		if (ii[hh[h]] < i || ii[hh[h]] == i && jj[hh[h]] <= j)
			lower = h;
		else
			upper = h;
	}
	return hh[lower];
}

int *ej[N], eo[N];
int sz[N];
int uu[N][K + 1], ta[N][K + 1], tb[N][K + 1], kk[N];
long long *ss[N], *pp[N]; int nn_[N];
int n_, c, t;

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;
}

void remove_(int i, int j) {
	int o;

	for (o = eo[i]; o--; )
		if (ej[i][o] == j) {
			eo[i]--;
			while (o < eo[i])
				ej[i][o] = ej[i][o + 1], o++;
			return;
		}
}

void dfs1(int p, int i) {
	int o, centroid;

	sz[i] = 1, centroid = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			dfs1(i, j);
			sz[i] += sz[j];
			if (sz[j] * 2 > n_)
				centroid = 0;
		}
	}
	if ((n_ - sz[i]) * 2 > n_)
		centroid = 0;
	if (centroid)
		c = i;
}

void dfs2(int p, int i, int k, int u) {
	int o;

	uu[i][k] = u;
	ta[i][k] = t++;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs2(i, j, k, u);
	}
	tb[i][k] = t;
}

void cd(int n, int i, int k) {
	int o;

	n_ = n, dfs1(-1, i), i = c;
	kk[i] = k;
	t = 0, dfs2(-1, i, k, i);
	nn_[i] = 1;
	while (nn_[i] <= n)
		nn_[i] <<= 1;
	ss[i] = (long long *) malloc(nn_[i] * 2 * sizeof *ss[i]);
	pp[i] = (long long *) malloc(nn_[i] * 2 * sizeof *pp[i]);
	memset(ss[i], 0, nn_[i] * 2 * sizeof *ss[i]);
	memset(pp[i], 0x3f, nn_[i] * 2 * sizeof *pp[i]);
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		remove_(j, i);
		cd(sz[j] < sz[i] ? sz[j] : n - sz[i], j, k + 1);
	}
}

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

	ss[u][i] = ss[u][l] + ss[u][r];
	pp[u][i] = min(pp[u][l], pp[u][r] == INF ? INF : ss[u][l] + pp[u][r]);
}

void add_(int u, int i, int x) {
	i += nn_[u];
	ss[u][i] += x, pp[u][i] = pp[u][i] == INF ? INF : ss[u][i];
	while (i > 1)
		pul(u, i >>= 1);
}

void toggle_(int u, int i) {
	i += nn_[u];
	pp[u][i] = pp[u][i] == INF ? ss[u][i] : INF;
	while (i > 1)
		pul(u, i >>= 1);
}

long long query_(int u, int r) {
	int l;
	long long s;

	l = 0, s = 0;
	for (l += nn_[u], r += nn_[u]; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0)
			s += ss[u][r--];
	return s;
}

void add(int i, int j, int x) {
	int k, u, tmp;

	for (k = min(kk[i], kk[j]); k >= 0; k--) {
		u = uu[i][k];
		if (ta[i][k] > ta[j][k])
			tmp = i, i = j, j = tmp;
		add_(u, ta[j][k], x), add_(u, tb[j][k], -x);
	}
}

void toggle(int i) {
	int k, u;

	for (k = kk[i]; k >= 0; k--) {
		u = uu[i][k];
		toggle_(u, ta[i][k]);
	}
}

long long query(int i) {
	int k, u;
	long long ans;

	ans = INF;
	for (k = kk[i]; k >= 0; k--) {
		u = uu[i][k];
		ans = min(ans, query_(u, ta[i][k]) + pp[u][1]);
	}
	if (ans == INF)
		ans = -1;
	return ans;
}

int main() {
	int q, h, i, j, tmp;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d%d", &i, &j, &ww[h]), i--, j--;
		if (i > j)
			tmp = i, i = j, j = tmp;
		ii[h] = i, jj[h] = j;
		append(i, j), append(j, i);
	}
	for (h = 0; h < n - 1; h++)
		hh[h] = h;
	sort(hh, 0, n - 1);
	cd(n, 0, 0);
	for (h = 0; h < n - 1; h++)
		add(ii[h], jj[h], ww[h]);
	while (q--) {
		int t, w;

		scanf("%d", &t);
		if (t == 1) {
			scanf("%d", &i), i--;
			printf("%lld\n", query(i));
		} else if (t == 2) {
			scanf("%d", &i), i--;
			toggle(i);
		} else {
			scanf("%d%d%d", &i, &j, &w), i--, j--;
			if (i > j)
				tmp = i, i = j, j = tmp;
			h = search(i, j);
			add(ii[h], jj[h], w - ww[h]);
			ww[h] = w;
		}
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.c: In function 'search':
Main.c:49:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   49 |   if (ii[hh[h]] < i || ii[hh[h]] == i && jj[hh[h]] <= j)
      |                        ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
Main.c: In function 'append':
Main.c:66:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   66 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:207:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:211:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |   scanf("%d%d%d", &i, &j, &ww[h]), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:226:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
Main.c:228:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  228 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~
Main.c:231:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  231 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~
Main.c:234:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  234 |    scanf("%d%d%d", &i, &j, &w), i--, j--;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 18 / 18
• Subtask 6: 32 / 32