結果
問題 |
No.3025 Chocol∀te
|
ユーザー |
![]() |
提出日時 | 2025-02-15 20:22:20 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,061 bytes |
コンパイル時間 | 3,240 ms |
コンパイル使用メモリ | 185,380 KB |
実行使用メモリ | 37,832 KB |
最終ジャッジ日時 | 2025-02-15 20:23:00 |
合計ジャッジ時間 | 34,800 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 7 WA * 13 RE * 57 |
ソースコード
#include <iostream> #include <algorithm> #include <atcoder/all> #include <tuple> #include <map> using namespace std; using namespace atcoder; using ll = long long; ll N, M, Q, A[100009], ans[100009]; map<int, int> mp[100009]; //connect; vector<vector<int>> G, lG; ll query[100009], t[100009], u[100009]; int sqrtM = 100; int main(){ cin >> N >> M; G.resize(N + 1); for(int i = 1; i <= N; i++){ ll a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); mp[a][b] = 1; mp[b][a] = 1; } for(int i = 1; i <= N; i++) cin >> A[i]; lG.resize(N + 1); cin >> Q; for(int q = 1; q <= Q; q++){ cin >> query[q]; if(query[q] == 1){ cin >> t[q] >> u[q]; if(mp[t[q]][u[q]] == 0){ G[t[q]].push_back(u[q]); G[u[q]].push_back(t[q]); mp[t[q]][u[q]] = -1; mp[u[q]][t[q]] = -1; } } if(query[q] == 2){ cin >> t[q] >> u[q]; } if(query[q] == 3){ cin >> t[q]; } } for(int i = 1; i <= N; i++){ for(auto to : G[i]){ if((int)G[to].size() >= sqrtM) lG[i].push_back(to); if((int)G[i].size() >= sqrtM && mp[i][to] == 1) ans[i] += A[to]; } } /*for(int i = 1; i <= N; i++) cout << ans[i] << " "; cout << endl;*/ for(int q = 1; q <= Q; q++){ if(query[q] == 1){ if((int)G[t[q]].size() >= sqrtM){ ans[t[q]] -= A[u[q]] * mp[u[q]][t[q]]; } if((int)G[u[q]].size() >= sqrtM){ ans[u[q]] -= A[t[q]] * mp[t[q]][u[q]]; } mp[u[q]][t[q]] *= -1; mp[t[q]][u[q]] *= -1; } if(query[q] == 2){ for(auto to : lG[t[q]]){ if(mp[t[q]][to] == 1) ans[to] += u[q] - A[t[q]]; //差分 } A[t[q]] = u[q]; } if(query[q] == 3){ if((int)G[t[q]].size() >= sqrtM){ cout << ans[t[q]] << endl; }else{ ll ret = 0; for(auto to : G[t[q]]){ if(mp[t[q]][to] == 1) ret += A[to]; } cout << ret << endl; } } /*for(int i = 1; i <= N; i++) cout << ans[i] << " "; cout << endl;*/ } return 0; }