제출 #985606

#제출 시각아이디문제언어결과실행 시간메모리
985606crafticat다리 (APIO19_bridges)C++17
13 / 100
3076 ms10536 KiB
#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;
}
#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...