Submission #1281332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281332		Faisal_Saqib	Bridges (APIO19_bridges)	C++20	13 / 100	3093 ms	9536 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;
// }
vector<pair<ll,ll>> ma[N];
bool vis[N];
ll w[N];
ll sz=0,cw=0;
void dfs(int x,int p=-1)
{
    vis[x]=1;
    sz++;
    for(auto sza:ma[x])
    {
        int y=sza.second,i=sza.first;
        if(y==p or vis[y])continue;
        if(w[i]>=cw)
        {
            dfs(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;
        ma[i].clear();
    }
    // vector<vector<ll>> edg,qry;
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y>>w[i];
        ma[x].push_back({i,y});
        ma[y].push_back({i,x});
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int t;
        cin>>t;
        ll s,wq;
        cin>>s>>wq;
        if(t==1)
        {   w[s-1]=wq;
        }
        else
        {
            for(int i=1;i<=n;i++)vis[i]=0;
            cw=wq;
            sz=0;
            dfs(s);
            cout<<sz<<endl;
        }

        // 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: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27