結果
問題 | 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: parentstd::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';}}}