Submission #955509

#	Time	Username	Problem	Language	Result	Execution time	Memory
955509		bunhadasou	Bridges (APIO19_bridges)	C++14	14 / 100	80 ms	7932 KiB

bridges

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define PB push_back
#define EB emplace_back
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) (int)x.size()
#define TASK "cf"

using namespace std;

const int maxn=1e5+5;
vector<pair<pair<int,int>,int>> ds,query;
int n,m,q;
int Rank[maxn],par[maxn],ans[maxn];

void make_set(){
    for (int i=1;i<=n;i++) {
        par[i]=i;
        Rank[i]=1;
    }
}

int find(int x) {
    if (x==par[x]) return x; return par[x]=find(par[x]);
}

void UNION(int x,int y) {
    x=find(x);y=find(y);
    if (x==y) return ;
    if (Rank[x]<Rank[y]) swap(x,y);
    Rank[x]+=Rank[y];
    par[y]=x;
    return ;
}

bool cmp1(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b){
    return a.se>b.se;
}

bool cmp2(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b){
    return a.fi.se>b.fi.se;
}



signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    cin>>n>>m;
    make_set();
    for (int i=1;i<=m;i++) {
        int x,y,z; cin>>x>>y>>z;
        ds.PB(mp(mp(x,y),z));
    }
    cin>>q;
    for (int i=1;i<=q;i++) {
        int type,x,y; cin>>type>>x>>y;
        query.PB(mp(mp(x,y),i));
    }
    sort(all(ds),cmp1);
    sort(all(query),cmp2);
    int j=0;
    for (int i=0;i<q;i++) {
        int w=query[i].fi.se;
        while (j<m && ds[j].se>=w) {
            UNION(ds[j].fi.fi,ds[j].fi.se);
            j++;
        }
        ans[query[i].se]=Rank[find(query[i].fi.fi)];
    }
    for (int i=1;i<=q;i++) cout<<ans[i]<<"\n";


    return 0;

}

Compilation message (stderr)

bridges.cpp: In function 'int find(int)':
bridges.cpp:28:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   28 |     if (x==par[x]) return x; return par[x]=find(par[x]);
      |     ^~
bridges.cpp:28:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   28 |     if (x==par[x]) return x; return par[x]=find(par[x]);
      |                              ^~~~~~

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