Submission #965050

#	Time	Username	Problem	Language	Result	Execution time	Memory
965050		irmuun	Bridges (APIO19_bridges)	C++17	14 / 100	96 ms	18648 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct dsu{
    ll n;
    vector<ll>par,sz;
    dsu(ll n):n(n){
        par.resize(n+1);
        iota(all(par),0);
        sz.resize(n+1);
        fill(all(sz),1);
    }
    ll find(ll x){
        if(par[x]==x) return x;
        return par[x]=find(par[x]);
    }
    ll SZ(ll x){
        x=find(x);
        return sz[x];
    }
    bool same(ll x,ll y){
        x=find(x);
        y=find(y);
        return x==y;
    }
    void merge(ll x,ll y){
        x=find(x);
        y=find(y);
        if(x!=y){
            if(sz[x]<sz[y]) swap(x,y);
            sz[x]+=sz[y];
            par[y]=x;
        }
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m;
    cin>>n>>m;
    vector<pair<ll,ll>>adj[n+5];
    vector<array<ll,3>>edge;
    for(ll i=1;i<=m;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
        edge.pb({w,v,u});
    }
    ll q;
    cin>>q;
    vector<array<ll,3>>que;
    vector<ll>ans(q);
    ll cur=0;
    while(q--){
        ll t;
        cin>>t;
        if(t==1){
            ll b,r;
            cin>>b>>r;
        }
        else{
            ll s,w;
            cin>>s>>w;
            que.pb({w,s,cur++});
        }
    }
    sort(rall(que));
    sort(rall(edge));
    ll l=0;
    dsu ds(n);
    for(auto [w,s,ind]:que){
        while(l<m&&edge[l][0]>=w){
            ds.merge(edge[l][1],edge[l][2]);
            l++;
        }
        ans[ind]=ds.SZ(s);
    }
    for(ll i=0;i<que.size();i++){
        cout<<ans[i]<<"\n";
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:87:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(ll i=0;i<que.size();i++){
      |                ~^~~~~~~~~~~

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