Submission #716495

#	Time	Username	Problem	Language	Result	Execution time	Memory
716495		1zaid1	Bridges (APIO19_bridges)	C++17	13 / 100	3083 ms	110992 KiB

bridges

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

#define int long long
#define endl '\n'

const int M = 2e6+5, MOD = 998244353;
multiset<pair<int, int>> node[M];
int vis[M];

int dfs(int s, int x) {
    int ans = 1;
    vis[s] = true;
    for (auto [i, y]:node[s]) {
        if (!vis[i] && y >= x) ans += dfs(i, x);
    } return ans;
}

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

    int n, m;
    cin >> n >> m;

    vector<array<int, 3>> E;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        node[a].insert({b, c});
        node[b].insert({a, c});
        E.push_back({a, b, c});
    }

    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x;

        if (x == 1) {
            cin >> x >> y;
            auto &[a, b, c] = E[x-1];
            node[a].erase(node[a].find({b, c}));
            node[b].erase(node[b].find({a, c}));
            node[a].insert({b, y});
            node[b].insert({a, y});
            c = y;
        } else {
            cin >> x >> y;
            cout << dfs(x, y) << endl;
            for (int i = 1; i <= n; i++) vis[i] = 0;
        }
    }

    return 0;
}
/*
7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
12
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
1 5 2
1 3 1
2 2 4
2 4 2
1 8 1
2 1 1
2 1 3
-----
3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2
*/

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