제출 #1160675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160675		sleepntsheep	Grapevine (NOI22_grapevine)	C11	100 / 100	1402 ms	268152 KiB

Main

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

#define N 200005
#define NL (N*18)

int n, qqq, n0, *eh[N], eo[N], e2v[N], w[N]
	, sz[N], dead[N], dfn[20][N], out[20][N]
	, cdep[N], cpar[N], nn[N], fruity[N], A[NL], L[NL], R[NL], rt[N], ii;

void sset(int *v, int l, int r, int p, int k) {
	if (! *v)
		*v = ++ii;
	if (l == r) {
		A[*v] = k;
		return;
	}
	if (p <= (l + r) / 2)
		sset(L + *v, l, (l + r) / 2, p, k);
	else
		sset(R + *v, (l + r) / 2 + 1, r, p, k);
}

int sget(int v, int l, int r, int k) {
	if (l == r)
		return A[v];
	if (k <= (l + r) / 2)
		return sget(L[v], l, (l + r) / 2, k);
	return sget(R[v], (l + r) / 2 + 1, r, k);
}

void init() {
	static int uu[N], vv[N], ww[N];
	scanf("%d%d", &n, &qqq);

	n0 = n;

	for (int i = 1; i < n0; ++i) {
		scanf("%d%d%d", &uu[i], &vv[i], &ww[i]);
		e2v[i] = ++n;
		++eo[uu[i]];
		++eo[n];
		++eo[n];
		++eo[vv[i]];
		w[n] = ww[i];
		sset(&rt[uu[i]], 0, n0, vv[i], n);
		sset(&rt[vv[i]], 0, n0, uu[i], n);
	}

	for (int i = 1; i <= n; ++i) {
		eh[i] = (int*)malloc(sizeof **eh * eo[i]);
		eo[i] = 0;
	}

	for (int i = 1; i < n0; ++i) {
		eh[uu[i]][eo[uu[i]]++] = e2v[i];
		eh[vv[i]][eo[vv[i]]++] = e2v[i];
		eh[e2v[i]][eo[e2v[i]]++] = uu[i];
		eh[e2v[i]][eo[e2v[i]]++] = vv[i];
	}
}

void dfs(int u, int p) {
	sz[u] = 1;
	for (int *v = eh[u]; eo[u] + eh[u] > v; ++v)
		if (! dead[*v] && *v != p)
			dfs(*v, u), sz[u] += sz[*v];
}

int get_centroid(int u, int p, int tsz) {
	for (int *v = eh[u]; eo[u] + eh[u] > v; ++v)
		if (! dead[*v] && *v != p && sz[*v] * 2 >= tsz)
			return get_centroid(*v, u, tsz);
	return u;
}

void dfs_tour(int u, int p, int cen) {
	dfn[cdep[cen]][u] = nn[cen]++;

	for (int *v = eh[u]; eo[u] + eh[u] > v; ++v)
		if (! dead[*v] && *v != p)
			dfs_tour(*v, u, cen);

	out[cdep[cen]][u] = nn[cen];
}

typedef struct {
	long long *t, *lz;
	int n, l, r;
} miku;

miku *mi[N];

miku *miku_new(int n, int l, int r) {
	miku *m = (miku *)malloc(sizeof *m);

	m->n = n;
	m->l = l;
	m->r = r;

	m->t = (long long*) calloc(sizeof m->t[0], n * 4);
	m->lz = (long long*) calloc(sizeof m->lz[0], n * 4);
	return m;
}

void miku_pus(miku *m, int v, int l, int r) {
	if (! m->lz[v]) return;
	m->t[v] += m->lz[v];
	if (l != r) {
		m->lz[2 * v + 1] += m->lz[v];
		m->lz[2 * v + 2] += m->lz[v];
	}
	m->lz[v] = 0;
}

void miku_internal_range_add_(miku *m, int v, int l, int r, int x, int y, long long k) {
	miku_pus(m, v, l, r);
	if (r < x || y < l) return;
	if (x <= l && r <= y) {
		m->lz[v] = k;
		miku_pus(m, v, l, r);
		return;
	}
	miku_internal_range_add_(m, 2 * v + 1, l, (l + r) / 2, x, y, k);
	miku_internal_range_add_(m, 2 * v + 2, (l + r) / 2 + 1, r, x, y, k);
	m->t[v] = m->t[2 * v + 1] < m->t[2 * v + 2] ? m->t[2* v + 1] : m->t[2 * v + 2];
}

void miku_range_add(miku *m, int x, int y, long long k) {
	miku_internal_range_add_(m, 0, m->l, m->r, x, y, k);
}

long long miku_min(miku *m) {
	miku_pus(m, 0, m->l, m->r);
	return m->t[0];
}

long long miku_point(miku *m, int k) {
	int v = 0, l = m->l, r = m->r;
	miku_pus(m, v, l, r);
	while (l < r) {
		miku_pus(m, v, l, r);
		if (k <= (l + r) / 2) {
			v = v * 2 + 1;
			r = (l + r) / 2;
		} else {
			v = v * 2 + 2;
			l = (l + r) / 2 + 1;
		}
	}
	miku_pus(m, v, l, r);
	return m->t[v];
}

void dfs_weigh(int u, int p, int cen) {
	miku_range_add(mi[cen], dfn[cdep[cen]][u], out[cdep[cen]][u] - 1, w[u]);

	for (int *v = eh[u]; eo[u] + eh[u] > v; ++v)
		if (! dead[*v] && *v != p)
			dfs_weigh(*v, u, cen);
}

void centroid_decomposition(int u, int dep, int par) {
	dfs(u, u);
	u = get_centroid(u, u, sz[u]);
	dead[u] = 1;
	cpar[u] = par;
	cdep[u] = dep;

	dfs_tour(u, u, u);

	mi[u] = miku_new(nn[u], 0, nn[u]);
	miku_range_add(mi[u], 0, nn[u], 1e15);

	dfs_weigh(u, u, u);

	for (int *v = eh[u]; eo[u] + eh[u] > v; ++v)
		if (! dead[*v])
			centroid_decomposition(*v, dep + 1, u);
}


void do_queries() {
	while (qqq--) {
		int op, a, b, c;
		scanf("%d%d", &op, &a);
		if (op == 1) { /* seek */
			long long z = 1e15;

			for (int u = a; u; u = cpar[u]) {
				long long zc = miku_point(mi[u], dfn[cdep[u]][a])
						+ miku_min(mi[u]);
				if (miku_point(mi[u], dfn[cdep[u]][a]) >= 1e15)
					zc -= 1e15;
				zc -= w[u];

				if (zc < z)
					z = zc;
			}

			if (z < 1e15)
				printf("%lld\n", z);
			else
				puts("-1");

		} else if (op == 2) { /* soak */
			for (int u = a; u; u = cpar[u]) {
				miku_range_add(mi[u], dfn[cdep[u]][a], dfn[cdep[u]][a], fruity[a] ? 1e15 : -1e15);
			}
			fruity[a] ^= 1;
		} else { /* anneal */
			scanf("%d%d", &b, &c);
			int v = sget(rt[a], 0, n0, b);
			long long delta = c - w[v];
			for (int u = v; u; u = cpar[u]) {
				miku_range_add(mi[u], dfn[cdep[u]][v], out[cdep[u]][v] - 1, delta);
			}
			w[v] += delta;

		}
	}
}

int main() {
	init();
	centroid_decomposition(1, 0, 0);
	do_queries();


	return 0;
}

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

Main.c: In function 'init':
Main.c:34:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf("%d%d", &n, &qqq);
      |         ^~~~~~~~~~~~~~~~~~~~~~~
Main.c:39:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |                 scanf("%d%d%d", &uu[i], &vv[i], &ww[i]);
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c: In function 'do_queries':
Main.c:186:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |                 scanf("%d%d", &op, &a);
      |                 ^~~~~~~~~~~~~~~~~~~~~~
Main.c:212:25: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |                         scanf("%d%d", &b, &c);
      |                         ^~~~~~~~~~~~~~~~~~~~~

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