Submission #933763

#	Time	Username	Problem	Language	Result	Execution time	Memory
933763		irmuun	Bridges (APIO19_bridges)	C++17	13 / 100	3065 ms	20444 KiB

bridges

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m;
    cin>>n>>m;
    multiset<pair<ll,ll>>adj[n];
    vector<array<ll,3>>edge;
    for(ll i=0;i<m;i++){
        ll u,v,d;
        cin>>u>>v>>d;
        u--,v--;
        adj[u].insert({v,d});
        adj[v].insert({u,d});
        edge.pb({u,v,d});
    }
    vector<bool>used(n);
    ll q;
    cin>>q;
    while(q--){
        ll t;
        cin>>t;
        if(t==1){
            ll b,r;
            cin>>b>>r;
            b--;
            auto [u,v,d]=edge[b];
            adj[u].erase(adj[u].find({v,d}));
            adj[v].erase(adj[v].find({u,d}));
            edge[b][2]=r;
            d=r;
            adj[u].insert({v,d});
            adj[v].insert({u,d});
        }
        else{
            ll s,w;
            cin>>s>>w;
            s--;
            fill(all(used),0);
            function <void(ll)> dfs=[&](ll x){
                used[x]=true;
                for(auto [y,d]:adj[x]){
                    if(d>=w&&!used[y]){
                        dfs(y);
                    }
                }
            };
            dfs(s);
            ll ans=0;
            for(ll i=0;i<n;i++){
                if(used[i]==true){
                    ans++;
                }
            }
            cout<<ans<<"\n";
        }
    }
}

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