結果
| 問題 |
No.1197 モンスターショー
|
| ユーザー |
 Ricky_pon
|
| 提出日時 | 2020-08-22 17:26:41 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,484 bytes |
| コンパイル時間 | 2,700 ms |
| コンパイル使用メモリ | 202,576 KB |
| 最終ジャッジ日時 | 2025-01-13 10:38:13 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 RE * 1 |
| other | AC * 2 RE * 39 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:264:21: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘int’ [-Wformat=]
264 | scanf("%d", z);
| ~^ ~
| | |
| | int
| int*
main.cpp:238:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
238 | scanf("%d%d%d", &n, &K, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:240:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
240 | rep(i, K) scanf("%d", &c[i]), --c[i];
| ~~~~~^~~~~~~~~~~~~
main.cpp:252:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
252 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
main.cpp:262:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
262 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
main.cpp:264:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
264 | scanf("%d", z);
| ~~~~~^~~~~~~~~
main.cpp:264:18: warning: ‘z’ may be used uninitialized [-Wmaybe-uninitialized]
264 | scanf("%d", z);
| ~~~~~^~~~~~~~~
main.cpp:261:19: note: ‘z’ was declared here
261 | int x, y, z;
| ^
ソースコード
#include <bits/stdc++.h>
#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 second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
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;
}
constexpr lint mod = 1000000007;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;
template <typename T, typename E, typename F, typename F_INV, typename G>
struct LinkCutTree {
struct Node {
Node *par_ptr, *left_ptr, *right_ptr;
int idx;
bool rev;
T val, sum, subtree_sum;
Node()
: idx(-1),
par_ptr(nullptr),
left_ptr(nullptr),
right_ptr(nullptr),
rev(false),
val(T{}),
sum(T{}),
subtree_sum(T{}) {}
bool is_root() {
return !par_ptr ||
(par_ptr->left_ptr != this && par_ptr->right_ptr != this);
}
void print_data() {
int p = par_ptr ? par_ptr->idx : -1;
int l = left_ptr ? left_ptr->idx : -1;
int r = right_ptr ? right_ptr->idx : -1;
printf(
"id=%d, p=%d, l=%d, r=%d, rev=%d, val=%lld, sum_dist=%lld, "
"sum_num=%lld\n",
idx, p, l, r, rev, val.se, sum.fi, sum.se);
}
};
int n;
vector<Node> nodes;
F f;
F_INV f_inv;
G g;
LinkCutTree(int n, T et, F f, F_INV f_inv, G g)
: n(n), f(f), f_inv(f_inv), g(g) {
nodes.resize(n);
rep(i, n) {
nodes[i].idx = i;
nodes[i].val = nodes[i].sum = nodes[i].subtree_sum = et;
}
}
void toggle(Node *node) {
if (!node->rev) return;
if (node->left_ptr) node->left_ptr->rev ^= true;
if (node->right_ptr) node->right_ptr->rev ^= true;
swap(node->left_ptr, node->right_ptr);
node->rev = false;
}
void pull(Node *node) {
node->sum = node->subtree_sum;
if (node->left_ptr) node->sum = f(node->sum, node->left_ptr->sum);
if (node->right_ptr) node->sum = f(node->sum, node->right_ptr->sum);
node->sum.se += node->val.se;
}
void rotl(Node *node) {
Node *par = node->par_ptr, *grand_par = par->par_ptr;
if ((par->right_ptr = node->left_ptr)) node->left_ptr->par_ptr = par;
node->left_ptr = par;
par->par_ptr = node;
pull(par);
pull(node);
if ((node->par_ptr = grand_par)) {
if (grand_par->left_ptr == par) grand_par->left_ptr = node;
if (grand_par->right_ptr == par) grand_par->right_ptr = node;
pull(grand_par);
}
}
void rotr(Node *node) {
Node *par = node->par_ptr, *grand_par = par->par_ptr;
if ((par->left_ptr = node->right_ptr)) node->right_ptr->par_ptr = par;
node->right_ptr = par;
par->par_ptr = node;
pull(par);
pull(node);
if ((node->par_ptr = grand_par)) {
if (grand_par->left_ptr == par) grand_par->left_ptr = node;
if (grand_par->right_ptr == par) grand_par->right_ptr = node;
pull(grand_par);
}
}
void toggle_all(Node *node) {
if (node->is_root()) {
toggle(node);
return;
}
toggle_all(node->par_ptr);
toggle(node);
}
void splay(int i) {
Node *node = &nodes[i];
toggle_all(node);
while (!node->is_root()) {
Node *par = node->par_ptr;
if (par->is_root()) {
if (par->right_ptr == node)
rotl(node);
else
rotr(node);
return;
}
Node *grand_par = par->par_ptr;
if (par->left_ptr == node) {
if (grand_par->left_ptr == par)
rotr(par), rotr(node);
else
rotr(node), rotl(node);
} else {
if (grand_par->right_ptr == par)
rotl(par), rotl(node);
else
rotl(node), rotr(node);
}
}
}
Node *expose(int i) {
Node *child = nullptr;
for (Node *par = &nodes[i]; par; par = par->par_ptr) {
splay(par->idx);
if (child) par->subtree_sum = f_inv(par->subtree_sum, child->sum);
if (par->right_ptr)
par->subtree_sum = f(par->subtree_sum, par->right_ptr->sum);
par->right_ptr = child;
pull(par);
child = par;
}
splay(i);
return child;
}
void link(int child, int par) {
expose(child);
expose(par);
nodes[child].par_ptr = &nodes[par];
nodes[par].right_ptr = &nodes[child];
pull(&nodes[par]);
}
void cut(int child) {
expose(child);
Node *par = nodes[child].left_ptr;
nodes[child].left_ptr = nullptr;
par->par_ptr = nullptr;
pull(&nodes[child]);
}
void evert(int i) {
expose(i);
nodes[i].rev = true;
toggle(&nodes[i]);
}
void add_edge(int child, int par) {
evert(par);
evert(child);
link(child, par);
}
void del_edge(int child, int par) {
evert(par);
cut(child);
}
void update_val(int i, E x) {
evert(i);
nodes[i].val = g(nodes[i].val, x);
pull(&nodes[i]);
}
T get_subtree_sum(int child, int par) {
evert(par);
cut(child);
T ret = nodes[child].sum;
link(child, par);
return ret;
}
};
int main() {
int n, K, q;
scanf("%d%d%d", &n, &K, &q);
int c[K];
rep(i, K) scanf("%d", &c[i]), --c[i];
auto f = [](pll lhs, pll rhs) {
return make_pair(lhs.fi + rhs.fi + rhs.se, lhs.se + rhs.se);
};
auto f_inv = [](pll lhs, pll rhs) {
return make_pair(lhs.fi - rhs.fi - rhs.se, lhs.se - rhs.se);
};
auto g = [](pll lhs, lint rhs) { return make_pair(0, lhs.se + rhs); };
LinkCutTree<pll, lint, decltype(f), decltype(f_inv), decltype(g)> lct(
2 * n, {0, 0}, f, f_inv, g);
rep(_, n - 1) {
int a, b;
scanf("%d%d", &a, &b);
--a;
--b;
lct.add_edge(a, b);
}
rep(i, n) lct.add_edge(i, i + n);
rep(i, K) lct.update_val(c[i], 1);
rep(_, q) {
int x, y, z;
scanf("%d%d", &x, &y);
if (x == 1) {
scanf("%d", z);
--y;
--z;
lct.update_val(c[y], -1);
lct.update_val(z, 1);
c[y] = z;
} else {
--y;
auto tmp = lct.get_subtree_sum(y, y + n);
printf("%lld\n", tmp.fi);
}
}
}