結果
問題 | No.1790 Subtree Deletion |
ユーザー | 👑 ygussany |
提出日時 | 2021-12-19 00:37:04 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 170 ms / 3,000 ms |
コード長 | 2,484 bytes |
コンパイル時間 | 1,090 ms |
コンパイル使用メモリ | 30,960 KB |
実行使用メモリ | 22,392 KB |
最終ジャッジ日時 | 2023-10-13 18:31:38 |
合計ジャッジ時間 | 4,121 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,852 KB |
testcase_01 | AC | 2 ms
6,848 KB |
testcase_02 | AC | 2 ms
6,180 KB |
testcase_03 | AC | 167 ms
22,392 KB |
testcase_04 | AC | 166 ms
22,260 KB |
testcase_05 | AC | 167 ms
22,360 KB |
testcase_06 | AC | 170 ms
22,388 KB |
testcase_07 | AC | 165 ms
22,200 KB |
testcase_08 | AC | 25 ms
6,604 KB |
testcase_09 | AC | 154 ms
22,312 KB |
testcase_10 | AC | 153 ms
22,224 KB |
testcase_11 | AC | 154 ms
22,360 KB |
testcase_12 | AC | 80 ms
22,128 KB |
testcase_13 | AC | 106 ms
21,980 KB |
testcase_14 | AC | 44 ms
10,364 KB |
ソースコード
#include <stdio.h> typedef struct { int left, right, lb; long long sum; } lazy_seg_node; int leaf[200001]; void init_node(lazy_seg_node v[], int k, int l, int r) { v[k].left = l; v[k].right = r; v[k].sum = 0; v[k].lb = 1; if (l < r) { init_node(v, k << 1, l, (l + r) / 2); init_node(v, (k << 1) ^ 1, (l + r) / 2 + 1, r); } else leaf[l] = k; } void update_segment(lazy_seg_node v[], int k, int l, int r, int b) { int i, j; if (v[k].left > r || v[k].right < l) return; else if (v[k].left >= l && v[k].right <= r) { v[k].lb *= b; v[k].sum *= b; for (j = k, i = j >> 1; i > 0; j = i, i >>= 1) v[i].sum = v[j].sum ^ v[j^1].sum; } else { if (v[k].lb != 1) { j = k << 1; v[j].sum *= v[k].lb; v[j^1].sum *= v[k].lb; v[j].lb *= v[k].lb; v[j^1].lb *= v[k].lb; v[k].lb = 1; } update_segment(v, k << 1, l, r, b); update_segment(v, (k << 1) ^ 1, l, r, b); } } long long get_sum(lazy_seg_node v[], int k, int l, int r) { if (k == 1) update_segment(v, 1, l, r, 1); if (v[k].left > r || v[k].right < l) return 0; else if (v[k].left >= l && v[k].right <= r) return v[k].sum; else return get_sum(v, k << 1, l, r) ^ get_sum(v, (k << 1) ^ 1, l, r); } typedef struct Edge { struct Edge *next; int v; long long label; } edge; int DFS(edge* adj[], int u, int flag[], int first[], int last[], long long sum[]) { flag[u] = 1; first[u] = ++flag[0]; edge *p; for (p = adj[u]; p != NULL; p = p->next) { if (flag[p->v] == 0) DFS(adj, p->v, flag, first, last, sum); else sum[u] ^= p->label; } last[u] = ++flag[0]; } int main() { int i, N, u, w; long long l; edge *adj[100001] = {}, e[200001], *p; scanf("%d", &N); for (i = 0; i < N - 1; i++) { scanf("%d %d %lld", &u, &w, &l); e[i*2].v = w; e[i*2+1].v = u; e[i*2].label = l; e[i*2+1].label = l; e[i*2].next = adj[u]; e[i*2+1].next = adj[w]; adj[u] = &(e[i*2]); adj[w] = &(e[i*2+1]); } int first[100001], last[100001], flag[100001] = {}; long long sum[100001] = {}; DFS(adj, 1, flag, first, last, sum); lazy_seg_node v[524288]; init_node(v, 1, 1, N * 2); for (u = 1; u <= N; u++) v[leaf[first[u]]].sum = sum[u]; for (i = leaf[N*2]; i >= 1; i--) if (v[i].left < v[i].right) v[i].sum = v[i<<1].sum ^ v[(i<<1)^1].sum; int Q, t, x; scanf("%d", &Q); for (i = 1; i <= Q; i++) { scanf("%d %d", &t, &x); if (t == 1) update_segment(v, 1, first[x], last[x], 0); else printf("%lld\n", get_sum(v, 1, first[x] + 1, last[x])); } fflush(stdout); return 0; }