Submission #974706

#	Time	Username	Problem	Language	Result	Execution time	Memory
974706		Abito	Bridges (APIO19_bridges)	C++17	14 / 100	70 ms	8188 KiB

bridges

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
//#define int long long
#define ll long long
typedef unsigned long long ull;
using namespace std;
struct query{
    int x,w,i;
};
struct edge{
    int x,y,w;
};
const int N=1e5+5;
int n,m,q,ans[N],sz[N],par[N];
query b[N];
bool cmp1(edge x,edge y){
    return x.w<y.w;
}
bool cmp2(query x,query y){
    return x.w>y.w;
}
int getpar(int x){
    if (x==par[x]) return x;
    return par[x]=getpar(par[x]);
}
void link(int x,int y){
    x=getpar(x);
    y=getpar(y);
    if (x==y) return;
    if (sz[x]>sz[y]) swap(x,y);
    sz[y]+=sz[x];
    par[x]=y;
    return;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>m;
    vector<edge> v(m);
    for (int i=0;i<m;i++) cin>>v[i].x>>v[i].y>>v[i].w;
    for (int i=1;i<=n;i++) sz[i]=1,par[i]=i;
    sort(v.begin(),v.end(),cmp1);
    //for (int i=0;i<m;i++) cout<<v[i].x<<' '<<v[i].y<<endl;
    cin>>q;
    for (int i=1;i<=q;i++){
        cin>>b[i].x>>b[i].x>>b[i].w;
        b[i].i=i;
    }
    sort(b+1,b+1+q,cmp2);
    for (int i=1;i<=q;i++){
        //cout<<"h";
        while (!v.empty()){
            if (v.back().w<b[i].w) break;
            link(v.back().x,v.back().y);
            v.ppb();
        }ans[b[i].i]=sz[getpar(b[i].x)];
    }
    for (int i=1;i<=q;i++) cout<<ans[i]<<endl;
    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