제출 #1031712

#제출 시각아이디문제언어결과실행 시간메모리
1031712stdfloat다리 (APIO19_bridges)C++17
13 / 100
3069 ms8132 KiB
#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';
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...