제출 #721790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
721790		alvingogo	다리 (APIO19_bridges)	C++14	14 / 100	125 ms	4308 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--;
    }
    sort(e.begin(),e.end(),[&](auto a,auto b){return a.sc>b.sc;});
    int q;
    cin >> q;
    vector<int> ans(q);
    vector<pair<int,pair<int,int> > > gg(q);
    for(int i=0;i<q;i++){
        cin >> gg[i].fs >> gg[i].fs >> gg[i].sc.sc;
        gg[i].fs--;
        gg[i].sc.fs=i;
    }
    sort(gg.begin(),gg.end(),[&](auto a,auto b){return a.sc.sc>b.sc.sc;});
    int l=0;
    DSU dsu;
    dsu.init(n);
    for(auto h:gg){
        while(l<m && e[l].sc>=h.sc.sc){
            dsu.merge(e[l].fs.fs,e[l].fs.sc);
            l++;
        }
        ans[h.sc.fs]=dsu.ss[dsu.find(h.fs)];
    }
    for(int i=0;i<q;i++){
        cout << ans[i] << '\n';
    }
    return 0;
}

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