Submission #267095

#	Time	Username	Problem	Language	Result	Execution time	Memory
267095		kimbj0709	Bridges (APIO19_bridges)	C++14	14 / 100	118 ms	13160 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
#define f first
#define s second
vector<int> ufds(maxn);
vector<int> s(maxn,1);
int find(int k){
    if(ufds[k]!=k){
        ufds[k] = find(ufds[k]);
    }
    return ufds[k];
}
void merge(int a,int b){
    int temp1 = find(a);
    int temp2 = find(b);
    if(temp1==temp2){
        return;
    }
    ufds[temp1] = temp2;
    s[temp2] += s[temp1];
}
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m,q;
    for(int i=0;i<ufds.size();i++){
        ufds[i] = i;
    }
    int input1,input2,input3;
    vector<pair<int,pair<int,int> > > edges;
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> input1 >> input2 >> input3;
        edges.push_back({input3,{input1,input2}});
    }
    sort(edges.begin(),edges.end());
    vector<pair<int,pair<int,int> > > queries;
    cin >> q;
    vector<int> ans(maxn);
    for(int i=0;i<q;i++){
        cin >> input1 >> input3 >> input2;
        queries.push_back({input2,{input3,i}});
    }
    sort(queries.begin(),queries.end());
    reverse(queries.begin(),queries.end());
    reverse(edges.begin(),edges.end());
    int currpos = 0;
    for(int i=0;i<queries.size();i++){
        while(currpos<edges.size()&&edges[currpos].f>=queries[i].f){
            merge(edges[currpos].s.f,edges[currpos].s.s);
            currpos++;
        }
        /*for(int j=1;j<=n;j++){
            cout << s[j] << ' ';
        }
        cout << endl;
        cout << find(queries[i].s.f) << "--\n";*/
        ans[queries[i].s.s] = s[find(queries[i].s.f)];
    }
    for(int i=0;i<q;i++){
        cout << ans[i] << "\n";
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int32_t main()':
bridges.cpp:28:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<ufds.size();i++){
      |                 ~^~~~~~~~~~~~
bridges.cpp:50:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0;i<queries.size();i++){
      |                 ~^~~~~~~~~~~~~~~
bridges.cpp:51:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         while(currpos<edges.size()&&edges[currpos].f>=queries[i].f){
      |               ~~~~~~~^~~~~~~~~~~~~

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