Submission #690533

#	Time	Username	Problem	Language	Result	Execution time	Memory
690533		thinh1711	Bridges (APIO19_bridges)	C++17	13 / 100	3090 ms	7428 KiB

bridges

#include <bits/stdc++.h>
#define reu(i,a,b) for (int i=a;i<=b;++i)
#define pb push_back
using namespace std;
int n,m;
const int mx=100002;
int bridge[mx];
vector<pair<int , int> > ke[mx];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    reu(i,1,m){
       int u,v,d;
       cin>>u>>v;
       ke[u].pb({v,i});
       ke[v].pb({u,i});
       cin>>d;
       bridge[i]=d;
     }
    int q;
    cin>>q;
    reu(i,1,q)
    {
        int typ;
        cin>>typ;
        if (typ==1){
            int v,w;
            cin>>v>>w;
            bridge[v]=w;
        }
        else {
            bool is[mx];
            int cnt=1;
            memset(is,true,sizeof(is));
            int w,s;
            cin>>s>>w;
            is[s]=false;
            queue<int> q;
            q.push(s);
            while (!q.empty()){
                int h=q.front();
                q.pop();
                for (auto x:ke[h])
                              if (is[x.first]==true) if (bridge[x.second]>=w){
                                    is[x.first]=false;
                                    q.push(x.first);
                                    ++cnt;
                                }
            }
            cout<<cnt<<"\n";
        }
    }
    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