Submission #729085

#	Time	Username	Problem	Language	Result	Execution time	Memory
729085		1075508020060209tc	Bridges (APIO19_bridges)	C++14	14 / 100	343 ms	16024 KiB

bridges

#include<bits/stdc++.h>

using namespace std;
#define int long long
int n;int m;int Q;

int ar[500005];int br[500005];int cr[500005];
int uf[500005];
int sz[500005];
int fin(int x){
if(uf[x]==x){return uf[x];}
uf[x]=fin(uf[x]);
return uf[x];
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
if(pa==pb){return;}
uf[pa]=pb;
sz[pb]+=sz[pa];
}



int qa[500005];int qw[500005];
int ans[500005];



signed main(){
cin>>n>>m;

vector<pair<int,pair<int,int>>>es;

for(int i=1;i<=m;i++){
    cin>>ar[i]>>br[i]>>cr[i];
    es.push_back({cr[i],{ar[i],br[i]} });
}
sort(es.begin(),es.end());
cin>>Q;
vector<pair<int,int>>qry;
for(int i=1;i<=Q;i++){
    int typ;
    cin>>typ>>qa[i]>>qw[i];
    qry.push_back({qw[i],i});
}
sort(qry.begin(),qry.end());reverse(qry.begin(),qry.end());
for(int i=1;i<=n;i++){
    uf[i]=i;sz[i]=1;ans[i]=1;
}
int qit=0;
for(int i=m-1;i>=0;i--){
    while(qit<qry.size()&&es[i].first<qry[qit].first){
        int id=qry[qit].second;
        ans[id]=sz[fin(qa[id])];
        qit++;
    }
    mrg(es[i].second.first,es[i].second.second);
}
while(qit<qry.size()){
    int id=qry[qit].second;
    ans[id]=sz[fin(qa[id])];
    qit++;
}


for(int i=1;i<=Q;i++){
    cout<<ans[i]<<endl;
}


}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:53:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     while(qit<qry.size()&&es[i].first<qry[qit].first){
      |           ~~~^~~~~~~~~~~
bridges.cpp:60:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 | while(qit<qry.size()){
      |       ~~~^~~~~~~~~~~

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