Submission #672718

#	Time	Username	Problem	Language	Result	Execution time	Memory
672718		jhnah917	Bridges (APIO19_bridges)	C++14	0 / 100	72 ms	11652 KiB

bridges

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

struct UnionFind{
    vector<int> p;
    UnionFind(int n) : p(n+1) { iota(p.begin(), p.end(), 0); }
    int find(int v){ return v == p[v] ? v : p[v] = find(p[v]); }
    void merge(int u, int v){ p[find(u)] = find(v); }
};

int N, M, Q, P[50505], S[50505], R[101010];
vector<tuple<int,int,int,int>> A;
int Find(int v){ return v == P[v] ? v : P[v] = Find(P[v]); }
void Merge(int u, int v){
    u = Find(u); v = Find(v);
    if(u != v) P[u] = v, S[v] += S[u];
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1,u,v,w; i<=M; i++) cin >> u >> v >> w, A.emplace_back(w, 1, u, v);
    cin >> Q;
    for(int i=1,op,s,w; i<=Q; i++) cin >> op >> s >> w, A.emplace_back(w, 0, s, i);
    sort(A.begin(), A.end(), greater<>());

    iota(P+1, P+N+1, 1);
    fill(S+1, S+N+1, 1);
    for(auto [w,t,a,b] : A){
        if(t == 0) Merge(a, b);
        else R[b] = S[Find(a)];
    }
    for(int i=1; i<=Q; i++) cout << R[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     for(auto [w,t,a,b] : A){
      |              ^

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