제출 #1202558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202558		Gray	다리 (APIO19_bridges)	C++20	13 / 100	3095 ms	7668 KiB

bridges

#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"
const ll MOD = 998244353;
const ll INF = 2e18;

vector<vector<ll>> A;
vector<array<ll, 3>> e;

void solve(){
    ll n, m; cin >> n >> m;
    e.resize(m); A.resize(n+1);
    for (ll i=0; i<m; i++){
        ll u, v, w; cin >> u >> v >> w; e[i] = {u, v, w};
        A[u].push_back(i); A[v].push_back(i);
    }
    ll q; cin >> q;
    vector<ll> vis(n+1);
    ll vs=0;
    while (q--){
        ll typ; cin >> typ;
        if (typ==1){
            ll b, r; cin >> b >> r; e[b-1][2]=r;
        }else{
            ll s, w; cin >> s >> w;
            queue<ll> que; que.push(s);
            ll cnt=0; vs++; vis[s]=vs;
            while (!que.empty()){
                auto cur = que.front(); que.pop(); cnt++;
                for (auto i:A[cur]){
                    ll v = e[i][0]^e[i][1]^cur;
                    if (vis[v]<vs and e[i][2]>=w){
                        vis[v]=vs; que.push(v);
                    }
                }
            }
            cout << cnt << ln;
        }
    }
}

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

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