Submission #934070

#	Time	Username	Problem	Language	Result	Execution time	Memory
934070		vjudge1	Bridges (APIO19_bridges)	C++11	13 / 100	3091 ms	9808 KiB

bridges

//holasoydember:D
//20/01/2024
#include <bits/stdc++.h>

#define pb push_back
#define all(n) n.begin(),n.end()
#define Z size()
#define S second
#define F first 
#define ll long long
#define fo(x, y, z) for(ll x=y; x<=z; x++)
#define of(x, y, z) for(ll x=y; x>=z; x--)

using namespace std;

void value(int in){cout<<((in)?"YES\n":"NO\n");return;}

const ll md=1e9+7, mod=998244353; 

ll n, m, k, xd, zd;
ll a[100005], b[100005];
string s;
set<ll> f, g;
vector<pair<ll,ll>> v[50005];
queue<ll> q;

void bfs(){
    while(!q.empty()){
        
        auto x=q.front();
        q.pop();
        //cout<<x<<' '<<zd<<"bfs\n";
        if(f.count(x))continue;
        f.insert(x);
        
        for(auto u:v[x]){
            //cout<<b[u.S]<<' ';
            if(xd>b[u.S] || f.count(u.F))continue;
            //cout<<'Y';
            q.push(u.F);
        }
        //cout<<"\n";
    }
    return;
}

void CD(){
    cin>>n>>m;
    
    fo(i,1,m){
        cin>>xd>>zd>>b[i];
        v[xd].pb({zd,i});
        v[zd].pb({xd,i});
    }
    
    cin>>k;
    
    while(k--){
        cin>>xd>>zd;
        if(xd==1){
            cin>>b[zd];
        }
        else{
            cin>>xd;
            
            q.push(zd);
            
            bfs();
            
            cout<<f.Z<<"\n";
            f.clear();
        }
    }
    
    return;
}

int main()
{
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    
    int t=1;
    //cin>>t;
    
    while(t--){
        CD();
    }

    return 0;
}

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