結果
問題 |
No.2912 0次パーシステントホモロジー
|
ユーザー |
![]() |
提出日時 | 2024-10-04 21:55:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 295 ms / 2,000 ms |
コード長 | 1,077 bytes |
コンパイル時間 | 6,278 ms |
コンパイル使用メモリ | 321,800 KB |
実行使用メモリ | 10,624 KB |
最終ジャッジ日時 | 2024-10-04 21:55:15 |
合計ジャッジ時間 | 8,729 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> #define rep(i, n) for(long long i = 0; i < n; i++) #define ALL(v) (v).begin(), (v).end() using namespace std; using lint = long long; int main() { int n, m; cin >> n >> m; vector<vector<tuple<int, int, int>>> es(100010); rep(i, m) { int u, v, w; cin >> u >> v >> w; es[w].emplace_back(0, u, v); } int t; cin >> t; rep(i, t) { int r; cin >> r; es[r].emplace_back(1, i, -1); } rep(i, 100010) { sort(ALL(es[i])); } atcoder::dsu uf(n); int cnt = n; vector<int> ans(t); rep(i, 100010) { rep(j, (int)es[i].size()) { if (get<0>(es[i][j]) == 0) { auto [type, u, v] = es[i][j]; if (!uf.same(u, v)) { uf.merge(u, v); cnt--; } } else { auto [type, id, hoge] = es[i][j]; ans[id] = cnt; } } } rep(i, t) { cout << ans[i] << endl; } }