結果

問題 No.3025 Chocol∀te
ユーザー iomir
提出日時 2025-02-15 09:39:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 736 ms / 2,000 ms
コード長 3,151 bytes
コンパイル時間 3,915 ms
コンパイル使用メモリ 290,004 KB
実行使用メモリ 60,132 KB
最終ジャッジ日時 2025-02-15 09:39:39
合計ジャッジ時間 31,060 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 77
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;

#define all(v) v.begin(),v.end()
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using vll=vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll,ll>;
using vp=vector<pair<ll, ll>>;
//using mint=modint1000000007;
//using mint=modint998244353;

const ll INF=1ll<<60;
ll mod10=1e9+7;
ll mod99=998244353;
const double PI = acos(-1);

#define rep(i,n) for (ll i=0;i<n;++i)
#define per(i,n) for(ll i=n-1;i>=0;--i)
#define rep2(i,a,n) for (ll i=a;i<n;++i)
#define per2(i,a,n) for (ll i=a;i>=n;--i)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }

bool solve(){
   ll N,M;cin>>N>>M;
   vll cnt(N);
   vll X(M),Y(M);rep(i,M) cin>>X[i]>>Y[i],X[i]--,Y[i]--;
   vll A(N);rep(i,N) cin>>A[i];
   ll Q;cin>>Q;
   vll T(Q),U(Q),V(Q);
   rep(i,Q){
      cin>>T[i];
      if(T[i]==1){
         cin>>U[i]>>V[i],U[i]--;V[i]--;
      }else if(T[i]==2){
         cin>>U[i]>>V[i];
         U[i]--;
      }else{
         cin>>U[i];U[i]--;
      }
   }

   rep(i,M) cnt[X[i]]++,cnt[Y[i]]++;
   rep(i,Q) if(T[i]==1) cnt[U[i]]++,cnt[V[i]]++;

   ll B=300;
   vll big(N);rep(i,N) if(cnt[i]>=B) big[i]=1;

   vector<unordered_set<ll>> ab(N);
   vector<unordered_set<ll>> abB(N);
   rep(i,M){
      ab[X[i]].insert(Y[i]);
      ab[Y[i]].insert(X[i]);
      if(big[X[i]]) abB[Y[i]].insert(X[i]);
      if(big[Y[i]]) abB[X[i]].insert(Y[i]);
   }
   vll ans(N);
   rep(i,M){
      if(big[Y[i]]==0) ans[X[i]]+=A[Y[i]];
      if(big[X[i]]==0) ans[Y[i]]+=A[X[i]];
   }


 
   rep(k,Q){
      ll i=k;
      if(T[k]==1){
         ll u=U[k],v=V[k];
         if(big[u]==0){
            if(ab[v].count(u)) ans[v]-=A[u];
            else ans[v]+=A[u];
         }
         if(big[v]==0){
            if(ab[v].count(u)) ans[u]-=A[v];
            else ans[u]+=A[v];
         }



         if(ab[u].count(v)) ab[u].erase(v);
         else ab[u].insert(v);
         if(ab[v].count(u)) ab[v].erase(u);
         else ab[v].insert(u);

         if(big[u]==1){
            if(abB[v].count(u)) abB[v].erase(u);
            else abB[v].insert(u);
         }
         if(big[v]==1){
            
            if(abB[u].count(v)) abB[u].erase(v);
            else abB[u].insert(v);
         }
         
      }else if(T[k]==2){
         if(big[U[i]]==1){
            A[U[i]]=V[i];
         }else{
            for(auto x:abB[U[i]]){
               ans[x]-=A[U[i]];
               ans[x]+=V[i];
            }
            A[U[i]]=V[i];
         }
      }else{
         if(big[U[i]]==0){
            ll ans2=0;
            for(auto x:ab[U[i]]){
               ans2+=A[x];
            }
            cout << ans2 << endl;
            
         }else{
            ll ans2=ans[U[i]];
            for(auto x:abB[U[i]]){
               ans2+=A[x];
            }
            cout<<ans2<<endl;
         }
      }
   }
   return 0;
}


int main(){
   cin.tie(0);
   ios::sync_with_stdio(false);
   ll T=1;//cin>>T;
   rep(i,T) solve();
}
0