Submission #934660

#	Time	Username	Problem	Language	Result	Execution time	Memory
934660		viktorchares	Bridges (APIO19_bridges)	C++17	0 / 100	3042 ms	11036 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back
#define endl "\n"
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define pb push_back
#define mp make_pair
#define fi first
#define se second
bool z=0;
const int MAXN=2e5;

bool vis[MAXN+5];
vector <int> bridge; //int weight [number of bridge];
vector <pair<int,int>> adj[MAXN +1]; //first to, second number of bridge, [from]
int n=0,cnt=0;

void explora(int v,int w){
    int siz=adj[v].size();
    for(int i=0;i<siz;i++){
        if(vis[adj[v][i].fi]==0 && bridge[adj[v][i].se]>=w){
            cnt++;
            vis[adj[v][i].fi]=1;
            explora(adj[v][i].fi,w);
         }   
    }
    return;
}


int main(){
    //ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
    int t=0,i=0,q=0,v=0,m=0,u=0,d=0,w=0,b=0;cin>>n>>m;
    bridge.reserve(m);
    for(i=1;i<=m;i++){
        cin>>u>>v>>d;
        bridge[i]=d;
        adj[u].pb(mp(v,i));
        adj[v].pb(mp(u,i));
    }
    //bridge first weight [number of bridge];
    //adj first to, second number of bridge, [from]
    cin>>q;
    for(i=0;i<q;i++){
        cin>>t;
        if(t==1){//weight changes
            cin>>b>>w;
            bridge[b]=w;
        }else if(t==2){
            cin>>u>>w;
            fill(vis,vis+n+3,false);
            vis[u]=1;
            cnt=1;
            explora(u,w);
            std::cout<<cnt<<"\n";
        }
        
    }


    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