Submission #893538

#	Time	Username	Problem	Language	Result	Execution time	Memory
893538		Warinchai	Bridges (APIO19_bridges)	C++14	0 / 100	480 ms	524288 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,pair<int,int> > >ed;
int p[100005];
int sz[100005];
int fp(int x){x==p[x]?x:p[x]=fp(p[x]);}
int un(int a,int b){sz[fp(b)]+=sz[fp(a)],p[fp(a)]=fp(b);}
int ans[100005];
vector<pair<int,pair<int,int> > >qr;
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        ed.push_back({c,{a,b}});
    }
    sort(ed.begin(),ed.end(),greater<pair<int,pair<int,int> > >());
    for(int i=1;i<=n;i++)p[i]=i,sz[i]=1;
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int t,s,w;
        cin>>t>>s>>w;
        qr.push_back({w,{s,i}});
    }
    sort(qr.begin(),qr.end(),greater<pair<int,pair<int,int> > >());
    int cur=0;
    for(int i=0;i<q;i++){
        int w=qr[i].first;
        int s=qr[i].second.first;
        int id=qr[i].second.second;
        while(cur<ed.size()&&ed[cur].first>=w){
            un(ed[cur].second.first,ed[cur].second.second);
            cur++;
        }
        ans[id]=sz[fp(s)];
    }
    for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
}

Compilation message (stderr)

bridges.cpp: In function 'int fp(int)':
bridges.cpp:6:39: warning: no return statement in function returning non-void [-Wreturn-type]
    6 | int fp(int x){x==p[x]?x:p[x]=fp(p[x]);}
      |                                       ^
bridges.cpp: In function 'int un(int, int)':
bridges.cpp:7:57: warning: no return statement in function returning non-void [-Wreturn-type]
    7 | int un(int a,int b){sz[fp(b)]+=sz[fp(a)],p[fp(a)]=fp(b);}
      |                                                         ^
bridges.cpp: In function 'int main()':
bridges.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         while(cur<ed.size()&&ed[cur].first>=w){
      |               ~~~^~~~~~~~~~

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