結果
問題 | No.3025 Chocol∀te |
ユーザー |
![]() |
提出日時 | 2025-02-14 23:16:15 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 121 ms / 2,000 ms |
コード長 | 2,526 bytes |
コンパイル時間 | 4,112 ms |
コンパイル使用メモリ | 323,408 KB |
実行使用メモリ | 16,300 KB |
最終ジャッジ日時 | 2025-02-14 23:23:02 |
合計ジャッジ時間 | 16,546 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 77 |
ソースコード
#include<bits/stdc++.h> namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include<atcoder/all> #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<vector<pair<int, bool>>> to(n); vector<P> xy(m); for (auto& [x, y] : xy) cin >> x >> y, x--, y--, to[x].emplace_back(y, false), to[y].emplace_back(x, false); VI a(n); rep(i, n) cin >> a[i]; int q; cin >> q; vector<tuple<int, int, int>> qs(q); for (auto& [t, x, y] : qs) { cin >> t; if (t == 1) { cin >> x >> y; x--, y--, to[x].emplace_back(y, false), to[y].emplace_back(x, false); } else if (t == 2) { cin >> x >> y; x--; } else { cin >> x; x--; } } rep(u, n) { sort(all(to[u])); to[u].erase(unique(all(to[u])), to[u].end()); } VI deg(n); rep(u, n) deg[u] = to[u].size(); vector<P> es; rep(u, n) for (auto [v, _] : to[u]) if (u < v) es.emplace_back(u, v); rep(u, n) to[u].clear(); for (auto [u, v] : es) { if (pair(deg[u], u) < pair(deg[v], v)) to[u].emplace_back(v, false); else to[v].emplace_back(u, false); } for (auto [x, y] : xy) { if (pair(deg[x], x) >= pair(deg[y], y)) swap(x, y); ranges::lower_bound(to[x], y, {}, &pair<int, bool>::first)->second = true; } VL s(n); rep(u, n) for (auto [v, used] : to[u]) if (used) { s[v] += a[u]; } for (auto [t, x, y] : qs) { if (t == 1) { if (pair(deg[x], x) >= pair(deg[y], y)) swap(x, y); bool& used = ranges::lower_bound(to[x], y, {}, &pair<int, bool>::first)->second; if (used) s[y] -= a[x]; else s[y] += a[x]; used ^= 1; } else if (t == 2) { int diff = y - a[x]; a[x] = y; for (auto [v, used] : to[x]) if (used) s[v] += diff; } else { ll ans = s[x]; for (auto [v, used] : to[x]) if (used) ans += a[v]; cout << ans << '\n'; } } }