結果
問題 | No.3025 Chocol∀te |
ユーザー |
|
提出日時 | 2025-02-14 22:39:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,024 ms / 2,000 ms |
コード長 | 2,866 bytes |
コンパイル時間 | 2,252 ms |
コンパイル使用メモリ | 208,552 KB |
実行使用メモリ | 40,412 KB |
最終ジャッジ日時 | 2025-02-14 22:40:22 |
合計ジャッジ時間 | 25,794 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 77 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define BL 512 template<class T> istream& operator >> (istream& is, vector<T>& vec) { for(T& x : vec) is >> x; return is; } template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { if(vec.empty()) return os; os << vec[0]; for(auto it = vec.begin(); ++it != vec.end(); ) os << ' ' << *it; return os; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<set<int>> S(n), T(n); for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; u--, v--; S[u].insert(v); S[v].insert(u); } vector<int> a(n); vector<bool> used(n); vector<ll> tot(n); cin >> a; for(int v = 0; v < n; v++){ if(S[v].size() >= BL){ used[v] = true; for(auto u : S[v]){ tot[v] += a[u]; T[u].insert(v); } } } int Q; cin >> Q; while(Q--){ int cmd; cin >> cmd; if(cmd == 1){ int u, v; cin >> u >> v; u--, v--; if(S[v].count(u)){ S[v].erase(u); S[u].erase(v); if(used[v]){ T[u].erase(v); tot[v] -= a[u]; } if(used[u]){ T[v].erase(u); tot[u] -= a[v]; } }else{ S[v].insert(u); S[u].insert(v); if(used[v]){ T[u].insert(v); tot[v] += a[u]; }else if(S[v].size() >= BL){ used[v] = true; tot[v] = 0; for(auto &&v2 : S[v]){ T[v2].insert(v); tot[v] += a[v2]; } } if(used[u]){ T[v].insert(u); tot[u] += a[v]; }else if(S[u].size() >= BL){ used[u] = true; tot[u] = 0; for(auto &&u2 : S[u]){ T[u2].insert(u); tot[u] += a[u2]; } } } }else if(cmd == 2){ int p, c; cin >> p >> c; p--; for(auto v : T[p]){ tot[v] -= a[p]; tot[v] += c; } a[p] = c; }else{ int v; cin >> v; v--; ll ans = 0; if(S[v].size() < BL){ for(auto &&u : S[v]) ans += a[u]; }else{ ans = tot[v]; } cout << ans << '\n'; } } }