Submission #893546

#	Time	Username	Problem	Language	Result	Execution time	Memory
893546		Warinchai	Bridges (APIO19_bridges)	C++14	14 / 100	171 ms	7924 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){return x==p[x]?x:p[x]=fp(p[x]);}
void un(int a,int b){
    if(fp(a)==fp(b))return;
    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 main()':
bridges.cpp:36: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]
   36 |         while(cur<ed.size()&&ed[cur].first>=w){
      |               ~~~^~~~~~~~~~

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