Submission #1281331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281331		Faisal_Saqib	Bridges (APIO19_bridges)	C++20	14 / 100	90 ms	14260 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
int par[N],sz[N],ans[N];
int get(int x)
{
    return (par[x]==x?x:par[x]=get(par[x]));
}
void join(int x,int y)
{
    x=get(x);
    y=get(y);
    if(x==y)return;
    sz[x]+=sz[y];
    par[y]=x;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        par[i]=i;sz[i]=1;
    }
    vector<vector<ll>> edg,qry;
    for(int i=0;i<m;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        edg.push_back({w,x,y});
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int t;
        cin>>t;
        ll s,w;
        cin>>s>>w;
        edg.push_back({w,-1,i,s});
    }
    sort(rbegin(edg),rend(edg));
    for(auto ty:edg)
    {
        if(ty[1]==-1)
        {
            // query
            ans[ty[2]]=sz[get(ty[3])];
        }
        else
        {
            // edge
            join(ty[1],ty[2]);
        }
    }
    for(int i=0;i<q;i++)
    {
        cout<<ans[i]<<' ';
    }
    cout<<endl;
}

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