Submission #1005049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005049		vjudge1	다리 (APIO19_bridges)	C++17	14 / 100	236 ms	10036 KiB

bridges

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

const int N = 1e5 + 10;

int n, m, wei[N], q, ans[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];
}

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;
    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--;
        }

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

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

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