제출 #1005054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1005054		vjudge1	다리 (APIO19_bridges)	C++17	27 / 100	240 ms	10036 KiB

bridges

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

const int N = 1e5 + 10;

int n, m, wei[N], q, ans, answer[N], par[N], sz[N];
vector<pair<int, int>> edges, srt_edges;
vector<pair<pair<int, int>, int>> query;
vector<int> g[N];
bool vis[N];

int root(int v){
    return (par[v] == -1 ? v : par[v] = root(par[v]));
}

void merge(int u, int v){
    if ((u = root(u)) == (v = root(v)))
        return;

    par[u] = v;
    sz[v] += sz[u];
}

void dfs(int v, int w){
    ans++;
    vis[v] = 1;
    for (int e : g[v]){
        if (wei[e] < w) continue;
        int u = edges[e].first + edges[e].second - v;
        if (vis[u]) continue;

        dfs(u, w);
    }
}

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

    for (int i = 1; i <= n; i ++)
        par[i] = -1, sz[i] = 1;

    for (int i = 0; i < m; i ++){
        int u, v, d;
        cin >> u >> v >> d;

        wei[i] = d;
        edges.push_back({u, v});
        srt_edges.push_back({d, i});
        g[u].push_back(i);
        g[v].push_back(i);
    }

    sort(srt_edges.begin(), srt_edges.end());

    cin >> q;

    if (n <= 1000 and m <= 1000 and q <= 10000){
        for (int i = 0; i < q; i ++){
            int t;
            cin >> t;

            if (t == 1){
                int e, w;
                cin >> e >> w;
                e--;
                wei[e] = w;
            }
            else{
                int s, w;
                cin >> s >> w;

                ans = 0;
                memset(vis, 0, sizeof vis);
                dfs(s, w);
                
                cout << ans << endl;
            }
        }
        return 0;
    }

    for (int i = 0; i < q; i ++){
        int t, s, w;
        cin >> t >> s >> w;
        query.push_back({{w, s}, i});
    }

    sort(query.begin(), query.end());
    reverse(query.begin(), query.end());
    int p = m - 1;
    for (int i = 0; i < q; i ++){
        while (p >= 0 and srt_edges[p].first >= query[i].first.first){
            int e = srt_edges[p].second;
            merge(edges[e].first, edges[e].second);
            p--;
        }

        answer[query[i].second] = sz[root(query[i].first.second)];
    }

    for (int i = 0; i < q; i ++)
        cout << answer[i] << endl;
}

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