제출 #672718

#제출 시각아이디문제언어결과실행 시간메모리
672718jhnah917다리 (APIO19_bridges)C++14
0 / 100
72 ms11652 KiB
#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";
}

컴파일 시 표준 에러 (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){
      |              ^
#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...