結果
問題 | No.2325 Skill Tree |
ユーザー |
|
提出日時 | 2023-05-28 14:04:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 233 ms / 3,000 ms |
コード長 | 2,522 bytes |
コンパイル時間 | 2,369 ms |
コンパイル使用メモリ | 184,628 KB |
実行使用メモリ | 20,736 KB |
最終ジャッジ日時 | 2024-12-26 23:14:10 |
合計ジャッジ時間 | 12,543 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; struct Kruskal_dsu { public: vector<vector<pair<int,int>>> pa; Kruskal_dsu() : _n(0) {} Kruskal_dsu(int n) : _n(n), parent_or_size(n, -1), dat(n, 1 << 30), pa(n) { for(int i = 0; i < n; i++){ pa[i].emplace_back(0, 1); } } bool merge(int u, int v, int w) { assert(0 <= u && u < _n); assert(0 <= v && v < _n); int x = leader(u), y = leader(v); if (x == y) return false; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; pa[x].emplace_back(w, -parent_or_size[x]); dat[y] = w; return true; } bool same(int v, int u) { assert(0 <= v && v < _n); assert(0 <= u && u < _n); return leader(v) == leader(u); } int leader(int v) { assert(0 <= v && v < _n); while(parent_or_size[v] >= 0)v = parent_or_size[v]; return v; } int size(int v, int w){ //cerr << v << '\n'; while(dat[v] <= w) v = parent_or_size[v]; //cerr << v << '\n'; pair<int,int> tmp = {w + 1, -1}; int j = lower_bound(pa[v].begin(), pa[v].end(), tmp) - pa[v].begin() - 1; return pa[v][j].second; } int size(int v) { assert(0 <= v && v < _n); return -parent_or_size[leader(v)]; } int max_edge(int u, int v){ int ans = 0; while(u != v){ if (dat[u] > dat[v]) std::swap(u, v); ans = dat[u], u = parent_or_size[u]; if(u < 0)return -1; } return ans; } private: int _n; // root node: -1 * component size // otherwise: parent std::vector<int> parent_or_size, dat; }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector<tuple<int,int,int>> a(N - 1); for(int i = 0; i + 1 < N; i++){ int l, v; cin >> l >> v; v--; a[i] = make_tuple(l, v, i + 1); } sort(a.begin(), a.end()); Kruskal_dsu uf(N); for(int i = 0; i + 1 < N; i++){ int u, v, l; tie(l, u, v) = a[i]; uf.merge(u, v, l); } int Q; cin >> Q; while(Q--){ int cmd, x; cin >> cmd >> x; if(cmd == 1){ cout << uf.size(0, x) << '\n'; }else{ x--; cout << uf.max_edge(0, x) << '\n'; } } }