Submission #66634369

Source Code Expand

Copy
#include <stdio.h>
#include <stdlib.h>
#define KI_MAX (1 << 19) /* 524288 */
int ki[KI_MAX * 2 - 1];
void ki_add(int pos, int value) {
  pos += KI_MAX - 1;
  ki[pos] += value;
  do {
    pos = (pos - 1) / 2;
    ki[pos] += value;
  } while (pos > 0);
}
int ki_sum_i(int idx, int ss, int se, int qs, int qe) {
  if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
    return ki[idx];
  } else if (se <= qs || qe <= ss) { /* 完全に外れている */
    return 0;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <stdio.h>
#include <stdlib.h>

#define KI_MAX (1 << 19) /* 524288 */

int ki[KI_MAX * 2 - 1];

void ki_add(int pos, int value) {
	pos += KI_MAX - 1;
	ki[pos] += value;
	do {
		pos = (pos - 1) / 2;
		ki[pos] += value;
	} while (pos > 0);
}

int ki_sum_i(int idx, int ss, int se, int qs, int qe) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return ki[idx];
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		return 0;
	} else {
		int sm = ss + (se - ss) / 2;
		int l = ki_sum_i(idx * 2 + 1, ss, sm, qs, qe);
		int r = ki_sum_i(idx * 2 + 2, sm, se, qs, qe);
		return l + r;
	}
}

int ki_sum(int qs, int qe) {
	return ki_sum_i(0, 0, KI_MAX, qs, qe);
}

struct edge_s {
	int to, idx;
};

int ec[312345];
struct edge_s* es[312345];

void ae(int f, int t, int idx) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = (struct edge_s){ t, idx };
}

int N;
int U[312345], V[312345];
int Q;
int query[312345][3];

int current_idx = 0;
int start_idx[312345], end_idx[312345];
int edge_to_node[312345];

void dfs(int node, int from) {
	int i;
	start_idx[node] = current_idx++;
	for (i = 0; i < ec[node]; i++) {
		if (es[node][i].to != from) {
			edge_to_node[es[node][i].idx] = es[node][i].to;
			dfs(es[node][i].to, node);
		}
	}
	end_idx[node] = current_idx;
}

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i < N; i++) {
		if (scanf("%d%d", &U[i], &V[i]) != 2) return 1;
		ae(U[i], V[i], i);
		ae(V[i], U[i], i);
	}
	if (scanf("%d", &Q) != 1) return 1;
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d", &query[i][0], &query[i][1]) != 2) return 1;
		if (query[i][0] == 1) {
			if (scanf("%d", &query[i][2]) != 1) return 1;
		}
	}
	dfs(1, 0);
	for (i = 1; i <= N; i++) {
		ki_add(start_idx[i], 1);
	}
	for (i = 0; i < Q; i++) {
		if (query[i][0] == 1) {
			ki_add(start_idx[query[i][1]], query[i][2]);
		} else if (query[i][0] == 2) {
			int node = edge_to_node[query[i][1]];
			int all = ki_sum(start_idx[1], end_idx[1]);
			int sub = ki_sum(start_idx[node], end_idx[node]);
			int other = all - sub;
			printf("%d\n", abs(sub - other));
		}
	}
	return 0;
}

Submission Info

Submission Time
Task F - Compare Tree Weights
User mikecat
Language C (gcc 12.2.0)
Score 500
Code Size 2297 Byte
Status AC
Exec Time 214 ms
Memory 45048 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 1
AC × 43
Set Name Test Cases
Sample example_00.txt
All example_00.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, hand_11.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt
Case Name Status Exec Time Memory
example_00.txt AC 0 ms 1780 KiB
hand_00.txt AC 199 ms 45048 KiB
hand_01.txt AC 158 ms 28776 KiB
hand_02.txt AC 189 ms 27120 KiB
hand_03.txt AC 163 ms 27076 KiB
hand_04.txt AC 214 ms 27824 KiB
hand_05.txt AC 208 ms 27824 KiB
hand_06.txt AC 1 ms 1672 KiB
hand_07.txt AC 193 ms 32620 KiB
hand_08.txt AC 181 ms 26340 KiB
hand_09.txt AC 182 ms 28420 KiB
hand_10.txt AC 182 ms 29236 KiB
hand_11.txt AC 177 ms 30780 KiB
random_00.txt AC 190 ms 29740 KiB
random_01.txt AC 196 ms 29832 KiB
random_02.txt AC 193 ms 29768 KiB
random_03.txt AC 196 ms 29748 KiB
random_04.txt AC 192 ms 29812 KiB
random_05.txt AC 171 ms 29388 KiB
random_06.txt AC 170 ms 29268 KiB
random_07.txt AC 173 ms 29204 KiB
random_08.txt AC 171 ms 29320 KiB
random_09.txt AC 173 ms 29160 KiB
random_10.txt AC 199 ms 27136 KiB
random_11.txt AC 196 ms 27160 KiB
random_12.txt AC 196 ms 27092 KiB
random_13.txt AC 203 ms 27056 KiB
random_14.txt AC 195 ms 27084 KiB
random_15.txt AC 197 ms 27048 KiB
random_16.txt AC 197 ms 27076 KiB
random_17.txt AC 193 ms 27092 KiB
random_18.txt AC 193 ms 27132 KiB
random_19.txt AC 198 ms 27156 KiB
random_20.txt AC 196 ms 27140 KiB
random_21.txt AC 205 ms 27064 KiB
random_22.txt AC 196 ms 27148 KiB
random_23.txt AC 202 ms 27132 KiB
random_24.txt AC 196 ms 27168 KiB
random_25.txt AC 196 ms 27168 KiB
random_26.txt AC 197 ms 27056 KiB
random_27.txt AC 201 ms 27144 KiB
random_28.txt AC 198 ms 27172 KiB
random_29.txt AC 194 ms 27048 KiB
Facebook Twitter Telegram Share

2025-06-10 (Tue)
07:59:39 +09:00

More…