Submission #985606

#	Time	Username	Problem	Language	Result	Execution time	Memory
985606		crafticat	Bridges (APIO19_bridges)	C++17	13 / 100	3076 ms	10536 KiB

bridges

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int,int>;
vector<vector<int>> g;
vector<tuple<int,int,int>> info;
vector<bool> vis;


int dfs(int x, int weight) {
    int sum = 1;
    vis[x] = true;

    for (auto childId : g[x]) {
        auto [c1, c2, w] = info[childId];
        if (c1 == x) swap(c1,c2);
        if (vis[c1]) continue;
        if (w < weight) continue;
        sum += dfs(c1,weight);
    }

    return sum;
}

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

    g.resize(n + 1);
    info.resize(m);

    for (int i = 0; i < m; ++i) {
        int a, b, w; cin >> a >> b >> w;
        g[a].emplace_back(i);
        g[b].emplace_back(i);
        info[i] = {a,b,w};
    }

    int q; cin >> q;
    for (int i = 0; i < q; ++i) {
        int t, a, b; cin >> t >> a >> b;
        if (t == 2) {
            vis.clear();
            vis.resize(n + 1);
            cout << dfs(a,b) << "\n";
        } else {
            auto &[from,to,weight] = info[a - 1];
            weight = b;
            info[a - 1] = {from,to,weight};
        }
    }

    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