Submission #934015

#	Time	Username	Problem	Language	Result	Execution time	Memory
934015		vjudge1	Bridges (APIO19_bridges)	C++17	13 / 100	3094 ms	11852 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

const ll MAXN = 5E4+16;
vector <pair <ll, ll> > adj[MAXN];
vll wei;
ll vis[MAXN];
ll timer=0;

ll dfs (ll u, ll w) {
    if (vis[u]==timer) return 0;
    vis[u]=timer;
    ll ans=1;
    for (auto [v, i] : adj[u]) {
        if (wei[i] < w) continue;
        ans += dfs(v, w);
    }
    return ans;
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    for (ll i = 0; i < m; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        adj[u].push_back({ v, i });
        adj[v].push_back({ u, i });
        wei.push_back(w);
    }
    ll Q;
    cin >> Q;
    while (Q--) {
        char type;
        cin >> type;
        switch (type) {
            case '1':
            {ll i, w;
            cin >> i >> w;
            i--;
            wei[i] = w;}
            break;
            case '2':
            {ll u, w;
            cin >> u >> w;
            u--;
            timer++;
            cout << dfs(u, w) << '\n';}
            break;
        }
    }
    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