結果
| 問題 | No.1641 Tree Xor Query |
| ユーザー |
 Ricky_pon
|
| 提出日時 | 2021-08-06 22:27:22 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 97 ms / 5,000 ms |
| コード長 | 5,515 bytes |
| コンパイル時間 | 2,224 ms |
| コンパイル使用メモリ | 210,760 KB |
| 最終ジャッジ日時 | 2025-01-23 15:50:47 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 18 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:210:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
210 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
main.cpp:212:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
212 | rep(i, n) scanf("%d", &c[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:216:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
216 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
main.cpp:227:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
227 | scanf("%d%d%d", &t, &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>#include <atcoder/segtree>#include <vector>template <class T = int>struct Edge {int from, to;T cost;int idx;Edge() = default;Edge(int from, int to, T cost = 1, int idx = 0): from(from), to(to), cost(cost), idx(idx) {}};template <class T = int>struct Graph {std::vector<std::vector<Edge<T>>> es;int edge_num;Graph(int n) : edge_num(0) { es.resize(n); }int size() { return es.size(); }void add_edge(int from, int to, T cost = 1, int idx = 0) {es[from].emplace_back(from, to, cost, idx);++edge_num;}std::vector<Edge<T>> edges() {std::vector<Edge<T>> tmp;for (int v = 0; v < (int)es.size(); ++v) {for (auto& e : es[v]) {tmp.push_back(e);}}if (tmp.size() >= 2 && tmp[0].idx == tmp[1].idx) {return tmp;}std::vector<Edge<T>> res(edge_num);for (auto& e : tmp) res[e.idx] = e;return res;}std::vector<Edge<T>>& operator[](int i) { return es[i]; }};#include <algorithm>#include <cassert>#include <vector>template <class T>bool chmax(T &a, const T &b) {if (a < b) {a = b;return true;}return false;}template <class T>bool chmin(T &a, const T &b) {if (a > b) {a = b;return true;}return false;}template <class T>T div_floor(T a, T b) {if (b < 0) a *= -1, b *= -1;return a >= 0 ? a / b : (a + 1) / b - 1;}template <class T>T div_ceil(T a, T b) {if (b < 0) a *= -1, b *= -1;return a > 0 ? (a - 1) / b + 1 : a / b;}template <typename T>struct CoordComp {std::vector<T> v;bool sorted;CoordComp() : sorted(false) {}int size() { return v.size(); }void add(T x) { v.push_back(x); }void build() {std::sort(v.begin(), v.end());v.erase(std::unique(v.begin(), v.end()), v.end());sorted = true;}int get_idx(T x) {assert(sorted);return lower_bound(v.begin(), v.end(), x) - v.begin();}T &operator[](int i) { return v[i]; }};struct HeavyLightDecomposition {public:std::vector<int> idx, par, head, out;HeavyLightDecomposition(Graph<> gr, int root = 0) {idx.resize(gr.size());par.resize(gr.size());head.resize(gr.size());out.resize(gr.size());sz_dfs(gr, root, -1);int cur = 0;idx[root] = cur++;head[root] = root;hld_dfs(gr, root, -1, root, cur);}int lca(int u, int v) {while (true) {if (idx[u] > idx[v]) std::swap(u, v);if (head[u] == head[v]) return u;v = par[head[v]];}}std::pair<std::vector<std::pair<int, int>>,std::vector<std::pair<int, int>>>get_path(int u, int v) {std::vector<std::pair<int, int>> up, down;while (true) {if (head[u] == head[v]) {if (idx[u] < idx[v])down.emplace_back(idx[u], idx[v] + 1);elseup.emplace_back(idx[v], idx[u] + 1);std::reverse(up.begin(), up.end());std::reverse(down.begin(), down.end());return {up, down};} else {if (idx[u] < idx[v]) {down.emplace_back(idx[head[v]], idx[v] + 1);v = par[head[v]];} else {up.emplace_back(idx[head[u]], idx[u] + 1);u = par[head[u]];}}}}private:int sz_dfs(Graph<> &gr, int v, int pv) {int ret = 1, max_sz = 0;for (int i = 0; i < (int)gr[v].size(); ++i) {if (gr[v][i].to == pv) continue;int tmp = sz_dfs(gr, gr[v][i].to, v);ret += tmp;if (chmax(max_sz, tmp)) std::swap(gr[v][0], gr[v][i]);}return ret;}void hld_dfs(Graph<> &gr, int v, int pv, int h, int &cur) {for (auto &e : gr[v]) {if (e.to == pv) continue;idx[e.to] = cur++;par[e.to] = v;head[e.to] = (gr[v][0].to == e.to ? h : e.to);hld_dfs(gr, e.to, v, head[e.to], cur);}out[v] = cur;}};#define For(i, a, b) for (int i = (int)(a); (i) < (int)(b); ++(i))#define rFor(i, a, b) for (int i = (int)(a)-1; (i) >= (int)(b); --(i))#define rep(i, n) For(i, 0, n)#define rrep(i, n) rFor(i, n, 0)#define fi first#define se secondusing namespace std;using lint = long long;using pii = pair<int, int>;using pll = pair<lint, lint>;using namespace atcoder;int op(int a, int b) { return a ^ b; }int e() { return 0; }int main() {int n, q;scanf("%d%d", &n, &q);vector<int> c(n);rep(i, n) scanf("%d", &c[i]);Graph<int> gr(n);rep(i, n - 1) {int a, b;scanf("%d%d", &a, &b);--a;--b;gr.add_edge(a, b, 1);gr.add_edge(b, a, 1);}HeavyLightDecomposition hld(gr);segtree<int, op, e> st(n);rep(i, n) st.set(hld.idx[i], c[i]);rep(i, q) {int t, x, y;scanf("%d%d%d", &t, &x, &y);--x;if (t == 1) {int idx = hld.idx[x];st.set(idx, st.get(idx) ^ y);} else {printf("%d\n", st.prod(hld.idx[x], hld.out[x]));}}}