https://atcoder.jp/contests/past202005-open/tasks/past202005_e
解説
https://atcoder.jp/contests/past202005-open/submissions/14066764
この問題では、競技プログラミングではよく出る無向グラフをうまく扱えるかが問われている問題。
競プロでは、無向グラフの辺については、隣接グラフで持つ方が多くの場面でよいとされている。
そうしておくと、今回の問題のクエリにも十分に対応可能である。
以下の配列が隣接グラフである。
E[cu] := 頂点cuから遷移可能な頂点の集合
クエリ1では、単純にc[x]を答える。O(1)
クエリ2では、E[x]にある頂点のcをc[x]で置き換える。O(N)
よって全体でO(QN)であり、間に合う。
int N, M, Q; vector<int> E[202]; int c[202]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M >> Q; rep(i, 0, M) { int a, b; cin >> a >> b; a--; b--; E[a].push_back(b); E[b].push_back(a); } rep(i, 0, N) cin >> c[i]; rep(_, 0, Q) { int t; cin >> t; if (t == 1) { int x; cin >> x; x--; printf("%d\n", c[x]); fore(to, E[x]) c[to] = c[x]; } else { int x, y; cin >> x >> y; x--; printf("%d\n", c[x]); c[x] = y; } } }