結果

問題 No.3025 Chocol∀te
ユーザー GOTKAKO
提出日時 2025-02-14 23:50:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 953 ms / 2,000 ms
コード長 4,222 bytes
コンパイル時間 2,417 ms
コンパイル使用メモリ 208,200 KB
実行使用メモリ 39,524 KB
最終ジャッジ日時 2025-02-14 23:51:09
合計ジャッジ時間 28,429 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 77
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,M; cin >> N >> M;
    vector<unordered_set<int>> Graph(N),Graph2(N);
    for(int i=0; i<M; i++){
        int u,v; cin >> u >> v;
        u--; v--;
        Graph.at(u).insert(v);
        Graph.at(v).insert(u);
    }
    vector<long long> A(N);
    for(auto &a : A) cin >> a;

    int B = 500;
    unordered_set<int> Big;
    vector<long long> answer(N);
    for(int i=0; i<N; i++){
        if(Graph.at(i).size() >= B){
            Big.insert(i);
            for(auto &to : Graph.at(i)) if(Graph.at(to).size() >= B) Graph2.at(i).insert(to);
        }
        else for(auto &to : Graph.at(i)) if(Graph.at(to).size() >= B) answer.at(to) += A.at(i);
    }

    int Q; cin >> Q;
    while(Q--){
        int t; cin >> t;
        if(t == 1){
            int u,v; cin >> u >> v; u--; v--;
            if(Graph.at(u).count(v)){
                Graph.at(u).erase(v);
                Graph.at(v).erase(u);
                if(Graph2.at(u).count(v)) Graph2.at(u).erase(v),Graph2.at(v).erase(u);
                if(Graph.at(u).size() < B && Graph.at(v).size() >= B) answer.at(v) -= A.at(u);
                swap(u,v);
                if(Graph.at(u).size() < B && Graph.at(v).size() >= B) answer.at(v) -= A.at(u);
                swap(u,v);

                if(Graph.at(u).size()+1 == B){
                    for(auto &to : Graph.at(u)) if(to != v && Graph.at(to).size() >= B){
                        answer.at(to) += A.at(u);
                        Graph2.at(u).erase(to);
                        Graph2.at(to).erase(u);
                    }
                    answer.at(u) = 0; Big.erase(u);
                }
                if(Graph.at(v).size()+1 == B){
                    for(auto &to : Graph.at(v)) if(to != u && Graph.at(to).size() >= B){
                        answer.at(to) += A.at(v);
                        Graph2.at(v).erase(to);
                        Graph2.at(to).erase(v);
                    }
                    answer.at(v) = 0; Big.erase(v);
                }
            }
            else{
                Graph.at(u).insert(v);
                Graph.at(v).insert(u);
                if(Graph.at(u).size() >= B && Graph.at(v).size() >= B){
                    Graph2.at(u).insert(v);
                    Graph2.at(v).insert(u);
                }
                if(Graph.at(u).size() > B && Graph.at(v).size() < B) answer.at(u) += A.at(v);
                swap(u,v);
                if(Graph.at(u).size() > B && Graph.at(v).size() < B) answer.at(u) += A.at(v);
                swap(u,v);
                if(Graph.at(u).size() == B){
                    for(auto &to : Graph.at(u)){
                        if(Graph.at(to).size() < B) answer.at(u) += A.at(to);
                        else if(to != v){
                            Graph2.at(u).insert(to),Graph2.at(to).insert(u);
                            answer.at(to) -= A.at(u);
                        }
                    }
                    Big.insert(u);
                }
                if(Graph.at(v).size() == B){
                    for(auto &to : Graph.at(v)){
                        if(Graph.at(to).size() < B) answer.at(v) += A.at(to);
                        else if(to != u){
                            Graph2.at(v).insert(to),Graph2.at(to).insert(v);
                            answer.at(to) -= A.at(v); 
                        }        
                    }
                    Big.insert(v);
                }
            }
        }
        if(t == 2){
            int p,a; cin >> p >> a; p--;
            int diff = a-A.at(p); A.at(p) = a;
            if(Graph.at(p).size() < B) for(auto &to : Graph.at(p)) if(Graph.at(to).size() >= B) answer.at(to) += diff;
        }
        if(t == 3){
            int v; cin >> v; v--;
            if(Big.count(v)){
                long long ans = answer.at(v);
                for(auto &to : Graph2.at(v)) ans += A.at(to);
                cout << ans << "\n";
            }
            else{
                long long ans = 0;
                for(auto &to : Graph.at(v)) ans += A.at(to);
                cout << ans << "\n";
            }
        }
    }
}
0