結果
問題 | No.2325 Skill Tree |
ユーザー |
|
提出日時 | 2023-05-28 15:16:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 596 ms / 3,000 ms |
コード長 | 1,829 bytes |
コンパイル時間 | 2,158 ms |
コンパイル使用メモリ | 209,044 KB |
最終ジャッジ日時 | 2025-02-13 12:53:38 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; struct UnionFind { std::vector<int> par; inline UnionFind(const size_t n) : par(n, -1) {} inline void reset(const size_t n) { par.assign(n, -1); } inline int root(const size_t x) noexcept { return (par[x] < 0 ? x : par[x] = root(par[x])); } inline bool unite(size_t x, size_t y) noexcept { x = root(x); y = root(y); if (x == y) return false; if (par[x] > par[y]) std::swap(x, y); par[x] += par[y]; par[y] = x; return true; } inline bool same(const size_t x, const size_t y) noexcept { return root(x) == root(y); } inline int size(const size_t x) noexcept { return -par[root(x)]; }; }; int main() { int n; cin >> n; UnionFind uf(n); vector<vector<int>> g(n); vector<int> type2(n); for (int i = 1; i < n; i++) { int l, a; cin >> l >> a; type2[i] = l; g[a - 1].push_back(i); uf.unite(a - 1, i); } queue<int> que; que.push(0); type2[0] = 0; while (!que.empty()) { auto cur = que.front(); que.pop(); for (auto to : g[cur]) { if (type2[to] < type2[cur]) { type2[to] = type2[cur]; } que.push(to); } } int exclude = 0; for (int i = 0; i < n; i++) { if (!uf.same(0, i)) { exclude++; type2[i] = -1; } } auto type1 = type2; sort(type1.begin(), type1.end()); int q; cin >> q; while (q--) { int type, x; cin >> type >> x; if (type == 1) { cout << (upper_bound(type1.begin(), type1.end(), x) - type1.begin()) - exclude << endl; } else { cout << type2[x - 1] << endl; } } }