結果
問題 | No.2325 Skill Tree |
ユーザー |
![]() |
提出日時 | 2023-05-28 15:57:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 411 ms / 3,000 ms |
コード長 | 2,673 bytes |
コンパイル時間 | 2,275 ms |
コンパイル使用メモリ | 174,140 KB |
実行使用メモリ | 9,084 KB |
最終ジャッジ日時 | 2024-12-27 10:01:08 |
合計ジャッジ時間 | 16,403 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
/*∧∧∩( ゚∀゚)/ キタ━━━━━━(゚∀゚)━━━━━━!!!!⊂ ノ ゆっくり見てってね!!!!!!!!(つ ノo (ノ\ ☆| o(⌒ ⌒ヽ / ☆\ (´⌒ ⌒ ⌒ヾ /('⌒ ; ⌒ ::⌒ )(´ ) ::: ) /☆─ (´⌒;: ::⌒`) :; )*/#include <bits/stdc++.h>using namespace std;#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)typedef long long ll;#define _GLIBCXX_DEBUGll l[200009], a[200009];bool f[200009];ll gcd(int i, vector<ll>& was, vector<int>& pnt) {f[i] = true;ll w, num;if(!f[a[i]]) {num = gcd(a[i], was, pnt);} else {num = was[a[i]];}if(num == -1) {return -1;}w = max(l[i], num);pnt.push_back(w);was[i] = w;return w;}int countElementsLessThanOrEqual(const vector<int>& nums, int a) {int left = 0;int right = nums.size() - 1;// 二分探索while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= a) {left = mid + 1;} else {right = mid - 1;}}// leftはa以下の要素の個数を表すreturn left;}int main() {ios::sync_with_stdio(false);std::cin.tie(nullptr);int n; cin >> n;rep(i, 2, n+1) {cin >> l[i] >> a[i];}vector<ll> was(n+1);rep(i, 1, n+1) {was[i] = -1;}vector<int> pnt;f[1] = true;was[1] = 0;pnt.push_back(0);rep(i, 2, n+1) {if(f[i]) continue;f[i] = true;ll num;if(!f[a[i]]) {num = gcd(a[i], was, pnt);} else {num = was[a[i]];}if(num == -1) {was[i] = -1;continue;}was[i] = max(l[i], num);pnt.push_back(was[i]);}sort(pnt.begin(), pnt.end());int q; cin >> q;while(q--) {int z; cin >> z;if(z == 1) {int x; cin >> x;int cnt = countElementsLessThanOrEqual(pnt, x);cout << cnt << endl;} else {int y; cin >> y;cout << was[y] << endl;}}}