Submission #721774

#	Time	Username	Problem	Language	Result	Execution time	Memory
721774		alvingogo	Bridges (APIO19_bridges)	C++14	13 / 100	3071 ms	2200 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct DSU{
    vector<int> bo,ss;
    void init(int x){
        bo.resize(x);
        iota(bo.begin(),bo.end(),0);
        ss.resize(x,1);
    }
    int find(int x){
        return bo[x]==x?x:bo[x]=find(bo[x]);
    }
    void merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y){
            return;
        }
        if(ss[x]<ss[y]){
            swap(x,y);
        }
        ss[x]+=ss[y];
        bo[y]=x;
    }
};
int main(){
    AquA;
    int n,m;
    cin >> n >> m;
    vector<pair<pair<int,int>,int> > e(m);
    for(int i=0;i<m;i++){
        cin >> e[i].fs.fs >> e[i].fs.sc >> e[i].sc;
        e[i].fs.fs--;
        e[i].fs.sc--;
    }
    int q;
    cin >> q;
    for(int i=0;i<q;i++){
        int t;
        cin >> t;
        if(t==1){
            int a,b;
            cin >> a >> b;
            a--;
            e[a].sc=b;
        }
        else{
            int a,b;
            cin >> a >> b;
            a--;
            DSU dsu;
            dsu.init(n);
            for(int j=0;j<m;j++){
                if(e[j].sc>=b){
                    dsu.merge(e[j].fs.fs,e[j].fs.sc);
                }
            }
            cout << dsu.ss[dsu.find(a)] << "\n";
        }
    }
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27