제출 #1343919

#제출 시각아이디문제언어결과실행 시간메모리
1343919Zero다리 (APIO19_bridges)C++20
0 / 100
3094 ms589824 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define pi pair<ll,ll>

struct tr{
    ll u, v, w;
};

const int N = 50001;
vector<tr> b;
vector<pi> a[N];

ll n, m;

void iterDFS(int start, ll w) {
    ll cnt = 0;
    stack<pi> st;  // {node, parent}
    st.push({start, -1});
    while(!st.empty()){
        auto [x, p] = st.top(); st.pop();
        cnt++;
        for(auto i : a[x]){
            if(i.ff != p && i.ss >= w)
                st.push({i.ff, x});
        }
    }
    cout << cnt << '\n';
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    b.reserve(m);

    for(ll i = 0; i < m; i++){
        ll q, w, e;
        cin >> q >> w >> e;
        b.pb({q, w, e});
        a[q].pb({w, e});
        a[w].pb({q, e});
    }

    ll t;
    cin >> t;
    while(t--){
        ll p, l, r;
        cin >> p >> l >> r;
        if(p == 1){
            ll u = b[l-1].u, v = b[l-1].v, old_w = b[l-1].w;

            for(auto &j : a[u])
                if(j.ff == v && j.ss == old_w){ j.ss = r; break; }
            for(auto &j : a[v])
                if(j.ff == u && j.ss == old_w){ j.ss = r; break; }

            b[l-1].w = r;
        }
        else{
            iterDFS(l, r);
        }
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...