結果
問題 |
No.3025 Chocol∀te
|
ユーザー |
![]() |
提出日時 | 2025-07-18 04:18:13 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,786 bytes |
コンパイル時間 | 1,166 ms |
コンパイル使用メモリ | 105,692 KB |
実行使用メモリ | 33,884 KB |
最終ジャッジ日時 | 2025-07-18 04:19:05 |
合計ジャッジ時間 | 42,597 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 TLE * 9 -- * 47 |
ソースコード
// # pragma GCC target("avx2") // # pragma GCC optimize("O3") // # pragma GCC optimize("unroll-loops") #include <iostream> #include <vector> #include <unordered_set> #include <cassert> using namespace std; const int B = 400; typedef long long ll; ll a[100010],ans[100010]; unordered_set<int> um[100010]; ll t[100010],u[100010],v[100010],p[100010],A[100010],C[100010]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int i,j,n,m; cin >> n >> m; for(i=0;i<m;i++){ int x,y; cin >> x >> y; x--; y--; um[x].insert(y); um[y].insert(x); } for(i=0;i<n;i++) cin >> a[i]; int q; cin >> q; int las = -1; auto ope = [&](int x,int y){ if(um[x].count(y)){ um[x].erase(y); um[y].erase(x); }else{ um[x].insert(y); um[y].insert(x); } }; auto calc = [&](){ for(int id=0;id<n;id++) ans[id] = 0; for(int id=0;id<n;id++){ for(int x:um[id]) ans[id] += a[x]; } }; for(i=0;i<n;i++) C[i] = a[i]; calc(); unordered_set<int> um_t; for(i=0;i<q;i++){ cin >> t[i]; if(t[i]==1){ cin >> u[i] >> v[i]; u[i]--; v[i]--; } if(t[i]==2){ cin >> p[i] >> A[i]; p[i]--; um_t.insert(p[i]); } if(t[i]==3){ int V; cin >> V; V--; ll x = ans[V]; // 辺の入れ替え -> 値の更新の順でクエリが来たとする (辺の入れ替えによる差分は全てaで計算して後でCにする) // 値の更新は隣接する頂点だけ見る for(j=las + 1;j<i;j++){ if(t[j]==1){ if(um[u[j]].count(v[j])){ if(u[j]==V) x -= a[v[j]]; if(v[j]==V) x -= a[u[j]]; }else{ if(u[j]==V) x += a[v[j]]; if(v[j]==V) x += a[u[j]]; } ope(u[j],v[j]); } if(t[j]==2) C[p[j]] = A[j]; } for(int ver:um_t){ if(um[V].count(ver)) x += C[ver] - a[ver]; } for(j=las + 1;j<i;j++){ if(t[j]==1) ope(u[j],v[j]); if(t[j]==2) C[p[j]] = a[p[j]]; } cout << x << "\n"; } if(i%B==B - 1){ for(j=las + 1;j<=i;j++){ // cout << "j == " << j << "\n"; if(t[j]==1) ope(u[j],v[j]); if(t[j]==2){ a[p[j]] = A[j]; C[p[j]] = A[j]; } } um_t.clear(); calc(); las = i; } // cout << "las == " << las << "\n"; } }