Submission #1044687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044687		vjudge1	Bridges (APIO19_bridges)	C++17	13 / 100	23 ms	12924 KiB

bridges

#include "bits/stdc++.h"
using namespace std;

#define int int64_t    
#define pb push_back

using lint=__int128_t;

const int lim=200100;
const int mod=1e9+7;

using pii=pair<int,int>;

pii edges[lim];

vector<pii*>v[lim];

int cnt,weg;
bool vis[lim];

void dfs(int node){
    cnt++;
    vis[node]=1;
    for(pii*p:v[node]){
        auto[f,s]=*p;
        if(!vis[f]&&weg<=s){
            dfs(f);
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);freopen(".out","w",stdout);
#endif
    int n,m;
    cin>>n>>m;
    if(n<=1000&&m<=1000){
        for(int i=0;i<m;i++){
            int x,y,w;
            cin>>x>>y>>w;
            edges[i<<1]={y,w};
            v[x].pb(edges+(i<<1));
            edges[(i<<1)+1]={x,w};
            v[y].pb(edges+(i<<1)+1);
        }
        int Q;
        cin>>Q;
        for(int i=0;i<Q;i++){
            int t,x,y;
            cin>>t>>x>>y;
            if(t==1){
                x--;
                x<<=1;
                edges[x].second=edges[x|1].second=y;
            }else{
                cnt=0;
                weg=y;
                for(int i=0;i<=n;i++)vis[i]=0;
                dfs(x);
                cout<<cnt<<"\n";
            }
        }
        return 0;
    }
    assert(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