Submission #1004975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004975		vjudge1	Bridges (APIO19_bridges)	C++17	13 / 100	3041 ms	10956 KiB

bridges

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

const int N = 1e5 + 10;

int n, m, wei[N], q, ans;
vector<pair<int, int>> edges;
vector<int> g[N];
bool vis[N];

void dfs(int v, int w){
    ans++;
    vis[v] = 1;
    for (int e : g[v]){
        if (wei[e] < w) continue;
        int u = edges[e].first + edges[e].second - v;
        if (vis[u]) continue;

        dfs(u, w);
    }
}

int main(){
    cin >> n >> m;

    for (int i = 0; i < m; i ++){
        int u, v, d;
        cin >> u >> v >> d;

        wei[i] = d;
        edges.push_back({u, v});
        g[u].push_back(i);
        g[v].push_back(i);
    }

    cin >> q;
    for (int i = 0; i < q; i ++){
        int t;
        cin >> t;

        if (t == 1){
            int e, w;
            cin >> e >> w;
            e--;
            wei[e] = w;
        }
        else{
            int s, w;
            cin >> s >> w;

            ans = 0;
            memset(vis, 0, sizeof vis);
            dfs(s, w);
            
            cout << ans << endl;
        }
    }
}

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