Submission #1005142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005142		vjudge1	Bridges (APIO19_bridges)	C++17	0 / 100	210 ms	7396 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=50005;
int const mod=1e9+7;

vector<int> com[N];
int rep[N];
int ans[N*2];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=n;i++){
        com[i].push_back(i);
        rep[i]=i;
    }
    array<int,3> edge[m];
    for (int i = 0; i < m; ++i)
    {
        int a,b,w;
        cin>>a>>b>>w;
        edge[i]={w,a,b};
    }
    sort(edge,edge+n);
    reverse(edge,edge+n);
    // reverse()
    int q;
    cin>>q;
    array<int,3> qr[q];
    for(int i=0;i<q;i++){
        int t,a,b;
        cin>>t>>a>>b;
        qr[i]={b,a,i};
    }
    sort(qr,qr+n);
    reverse(qr,qr+n);
    int cur=0;
    for (int i = 0; i < m; ++i)
    {
        while(cur<q && qr[cur][0]>edge[i][0]){
            ans[qr[cur][2]]=com[rep[qr[cur][1]]].size();
            cur++;
        }
        int u=rep[edge[i][1]];
        int v=rep[edge[i][2]];
        if(u!=v){
            if(com[u].size()<com[v].size())
                swap(u,v);
            for(int e:com[v]){
                com[u].push_back(e);
                rep[e]=u;
            }
            com[v].clear();
        }
    }
    while(cur<q){
        ans[qr[cur][2]]=com[rep[qr[cur][1]]].size();
        cur++;
    }
    for (int i = 0; i < q; ++i)
        cout<<ans[i]<<endl;
    return 0;
}

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