結果
問題 | No.2912 0次パーシステントホモロジー |
ユーザー |
|
提出日時 | 2024-10-04 22:38:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 971 bytes |
コンパイル時間 | 2,314 ms |
コンパイル使用メモリ | 202,248 KB |
最終ジャッジ日時 | 2025-02-24 15:30:26 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 8 WA * 15 |
ソースコード
#include <bits/stdc++.h>using namespace std;int par[200020];int siz[200020];int gs;void init(int N) {gs = N;iota(par, par + N, 0);fill(siz, siz + N, 1);}int root(int v) {return par[v] = (v == par[v] ? v : root(par[v]));}int merge(int a, int b) {a = root(a); b = root(b);if (a == b) return 0;if (siz[a] < siz[b]) swap(a, b);par[b] = a;siz[a] += siz[b];return 1;}int main () {int N, M;cin >> N >> M;init(N);std::vector<tuple<int, int, int>> eg(M);for (auto& [w, u, v] : eg) {cin >> u >> v >> w;}int Q;cin >> Q;int fl = 0;vector<int> R(Q);for (auto& r : R) cin >> r;vector<int> ID(Q);iota(ID.begin(), ID.end(), 0);sort(ID.begin(), ID.end(), [&](int i, int j) {return R[i] < R[j];});vector<int> ans(Q);for (auto& i : ID) {int r = R[i];while (fl < M && get<0>(eg[fl]) <= r) {fl ++;gs -= merge(get<1>(eg[fl]), get<2>(eg[fl]));}ans[i] = gs;}for (auto& a : ans) {cout << a << endl;}}