結果

問題 No.2325 Skill Tree
ユーザー shin3110
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*
              ∧∧∩ 
             ( ゚∀゚)/ キタ━━━━━━(゚∀゚)━━━━━━!!!!
               !!!!!!!!
             (
    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_DEBUG
ll 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;
}
}
// lefta
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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0