Submission #261313

#TimeUsernameProblemLanguageResultExecution timeMemory
261313rqi다리 (APIO19_bridges)C++14
59 / 100
3099 ms7976 KiB
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define mp make_pair
#define ins insert
#define f first
#define s second
#define pb push_back


const int mx = 100005;
const int SQ = sqrt(mx);
int n, m;
int u[mx];
int v[mx];
int d[mx];

int t[mx];
int b[mx];
int r[mx];
int s[mx];
int w[mx];
int ans[mx];
int mind[mx];

void ps(int x){
    cout << x << "\n";
}

struct DSU {
    vi e;
    void init(int n){
        e = vi(n+1, -1);
    }
    int get(int a){
        if(e[a] < 0) return a;
        e[a] = get(e[a]);
        return e[a];
    }
    int getSize(int a){
        a = get(a);
        return -e[a];
    }
    bool unite(int a, int b){
        a = get(a);
        b = get(b);
        if(a == b) return 0;
        if(-e[a] < -e[b]) swap(a, b);
        e[a]+=e[b];
        e[b] = a;
        return 1;
    }

};

set<pi> eds; //weight, index
bool notinc[mx];
int cursp[mx]; //weight of special edges

void INSERT(int ind){
    eds.ins(mp(d[ind], ind));
}

void ERASE(int ind){
    eds.erase(eds.find(mp(d[ind], ind)));
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> u[i] >> v[i] >> d[i];
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> t[i];
        if(t[i] == 1){
            cin >> b[i] >> r[i];
        }
        else{
            cin >> s[i] >> w[i];
        }
    }

    
    for(int i = 1; i <= m; i++){
        INSERT(i);
    }

    for(int i = 1; i <= q; i+=SQ){
        vpi speceds; //index, original weight
        for(int j = i; j < i+SQ; j++){
            if(t[j] == 1){
                notinc[b[j]] = 1;
            }
        }
        for(int j = 1; j <= m; j++){
            if(notinc[j]){
                speceds.pb(mp(j, d[j]));
            }
        }

        set<pair<pi, int>> queries;

        for(int j = i; j < i+SQ; j++){
            if(t[j] == 2){
                queries.ins(mp(mp(-w[j], s[j]), j));
            }
        }

        DSU bdsu;
        bdsu.init(n);

        auto it = eds.end();

        for(auto x: queries){
            int weight = -x.f.f;
            int node = x.f.s;
            int ind = x.s;
            while(it != eds.begin()){
                pi val = *(prev(it));
                if(val.f < weight){
                    break;
                }
                it = prev(it);
                if(notinc[val.s]) continue;
                bdsu.unite(u[val.s], v[val.s]);
            }
            for(auto x: speceds){
                cursp[x.f] = x.s;
            }
            for(int j = i; j < ind; j++){
                if(t[j] == 1){
                    if(notinc[b[j]]){
                        cursp[b[j]] = r[j];
                    }
                }
            }


            node = bdsu.get(node);
            bool flag = 0;
            vpi seds;
            for(auto x: speceds){
                if(cursp[x.f] >= weight){
                    seds.pb(mp(bdsu.get(u[x.f]), bdsu.get(v[x.f])));
                }
            }
            for(auto x: seds){
                if(x.f == node || x.s == node){
                    flag = 1;
                    break;
                }
            }
            if(flag == 0){
                ans[ind] = bdsu.getSize(node);
                continue;
            }
            DSU sdsu;
            sdsu.init(2*SQ);
            //map each relevant node
            for(auto x: seds){
                mind[x.f] = 0;
                mind[x.s] = 0;
            }
            int cnt = 0;
            for(auto x: seds){
                if(mind[x.f] == 0){
                    mind[x.f] = ++cnt;
                    sdsu.e[cnt] = -bdsu.getSize(x.f);
                }
                if(mind[x.s] == 0){
                    mind[x.s] = ++cnt; 
                    sdsu.e[cnt] = -bdsu.getSize(x.s);
                }
            }
            for(auto x: seds){
                sdsu.unite(mind[x.f], mind[x.s]);
            }
            ans[ind] = sdsu.getSize(mind[node]);
        }


        for(int j = i; j < i+SQ; j++){
            if(t[j] == 1){
                notinc[b[j]] = 0;
            }
        }
        //update eds
        for(int j = i; j < i+SQ; j++){
            if(t[j] == 1){
                ERASE(b[j]);
                d[b[j]] = r[j];
                INSERT(b[j]);
            }
        }
    }

    for(int i = 1; i <= q; i++){
        if(t[i] == 2){
            ps(ans[i]);
        }
    }

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...