Submission #1031712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031712		stdfloat	Bridges (APIO19_bridges)	C++17	13 / 100	3069 ms	8132 KiB

bridges

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

using ll = long long;

#define sz(v) (int)(v).size()

#define ff  first
#define ss  second
#define pii pair<int, int>

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

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

    vector<pair<int, int>> E[n];
    vector<int> bx(m), by(m), bd(m);
    for (int i = 0; i < m; i++) {
        cin >> bx[i] >> by[i] >> bd[i];

        E[--bx[i]].push_back({--by[i], bd[i]});
        E[by[i]].push_back({bx[i], bd[i]});
    }

    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;

        if (t == 1) {
            int b, r;
            cin >> b >> r; b--;

            for (int i = 0; i < sz(E[bx[b]]); i++) {
                if (E[bx[b]][i] == (pii){by[b], bd[b]}) {
                    E[bx[b]].erase(E[bx[b]].begin() + i);
                    break;
                }
            }
            for (int i = 0; i < sz(E[by[b]]); i++) {
                if (E[by[b]][i] == (pii){bx[b], bd[b]}) {
                    E[by[b]].erase(E[by[b]].begin() + i);
                    break;
                }
            }

            bd[b] = r;
            E[bx[b]].push_back({by[b], r});
            E[by[b]].push_back({bx[b], r});
        }
        else {
            int s, w;
            cin >> s >> w; s--;

            // cout << "\ns " << s + 1 << ' ' << w << endl;

            queue<int> q;
            vector<bool> vis(n);
            q.push(s); vis[s] = true;
            while (!q.empty()) {
                auto x = q.front(); q.pop();

                for (auto [i, d] : E[x]) {
                    if (w <= d && !vis[i]) {
                        q.push(i);
                        vis[i] = true;
                    }
                }
            }

            cout << count(vis.begin(), vis.end(), true) << '\n';
        }
    }
}

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