제출 #934670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
934670		viktorchares	다리 (APIO19_bridges)	C++17	13 / 100	3050 ms	10344 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#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.resize(m+1);
    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+1,false);
            vis[u]=1;
            cnt=1;
            explora(u,w);
            std::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