結果

問題 No.2325 Skill Tree
コンテスト
ユーザー yurina256
提出日時 2023-05-28 15:18:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 3,249 bytes
コンパイル時間 2,427 ms
コンパイル使用メモリ 175,660 KB
実行使用メモリ 15,104 KB
最終ジャッジ日時 2024-12-27 05:53:59
合計ジャッジ時間 22,352 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 RE * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std; 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define length size()
#define int long long
#define ll long long
int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}
template<typename T> string join(vector<T> &vec ,const string &sp){
    int si = vec.length;
    if(si==0){
        return "";
    }else{
        stringstream ss;
        rep(i,si-1){
            ss << vec[i] << sp;
        }
        ss << vec[si - 1];
        return ss.str();
    }
}
const int mod = 1000000007;
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int binToUInt(string s){
    int x = 0;
    rep(i,s.size()){
        x *= 2;
        if(s[i] == '1') x++;
    }
    return x;
}
signed main(void){
    int n;
    cin >> n;
    vector<pair<int,int>> waza(n+100);
    waza[0] = make_pair(0,0);
    rep(i,n-1){
        int l,a;
        cin >> l >> a;
        waza[i+1] = make_pair(l,a); //レベル,前提
    }
    /*sort(waza.begin(),waza.end(),[](a,b){
        return a.second > b.second;
    });*/
    vector<int> wb(n+100,0); //0=未 1=処理中 2=処理済
    wb[0] = 2;
    
    for(int i=1;i<n;i++){
        if(wb[i]==2) continue;
        stack<int> stk;
        int wt = i;
        bool flag = false;
        while(true){
            if(wb[wt] == 2){
                stk.push(wt);
                break;
            }
            if(wb[wt] == 1){
                flag = true;
                break;
            }
            else{
                stk.push(wt);
                wb[wt] = 1;
                wt = waza[wt].second-1;
            }
        }
        //cout << "!" << endl;
       int lv = 0;
        while(!stk.empty()){
            wt = stk.top();
            stk.pop();
            lv = max(lv,waza[wt].first);
            if(flag) lv = -1;
            waza[wt].first = lv;
            wb[wt] = 2;
          //  cout << wt << " " << endl;
        }
        //cout << endl;
    }
        //rep(i,n){
        //    cout << waza[i].first << " " << waza[i].second << endl;
        //}
        vector<int> imos(2*100005,0);
        rep(i,n){
            if(waza[i].first!=-1) imos[waza[i].first]++;
        }
        rep(i,imos.size()-2){imos[i+1] += imos[i];}
        
        
        //rep(i,n){
        //    cout << waza[i].first << "/" << waza[i].second << endl;
        //}
        //cout << join(imos,",") << endl;
        
        int q;
        cin>>q;
        rep(i,q){
            int type;
            cin >> type;
            int r;
            cin >> r;
            if(type==2) r --;
            //cout << "+" << type << " " << r << endl;
            if(type == 1){
                cout << imos[r] << endl;
            }
            if(type == 2){
                cout << waza[r].first << endl;
            }
        }
}
0