結果

問題 No.2325 Skill Tree
コンテスト
ユーザー yurina256
提出日時 2023-05-28 14:44:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,153 bytes
コンパイル時間 1,660 ms
コンパイル使用メモリ 176,924 KB
実行使用メモリ 8,092 KB
最終ジャッジ日時 2024-12-27 02:47:42
合計ジャッジ時間 13,755 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other WA * 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);
    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,0); //0=未 1=処理中 2=処理済
    wb[0] = 2;
    
    for(int i=1;i<n;i++){
        if(wb[i]==2) continue;
        int max_lv = 0;
        queue<int> que;
        int wt = i;
        while(true){
            max_lv = max(max_lv,waza[wt].first);
         //   cout << max_lv << " ";
            if(wb[wt] == 2) break;
            if(wb[wt] == 1){
                max_lv = -1;
                break;
            }
            else{
                que.push(wt);
                wb[wt] = 1;
                wt = waza[wt].second-1;
            }
        }
       // cout << "!" << endl;
        while(!que.empty()){
            wt = que.front();
        //    cout << wt << " ";
            que.pop();
            wb[wt] = 2;
            waza[wt].first = max_lv;
        }
       // cout << endl;
    }
        //rep(i,n){
        //    cout << waza[i].first << " " << waza[i].second << endl;
        //}
        vector<int> imos(50,0);
        rep(i,n){
            if(waza[i].first!=-1) imos[waza[i].first]++;
        }
        rep(i,imos.size()-1){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;
            r --;
            //cout << "+" << type << " " << r << endl;
            if(type == 1){
                cout << imos[r] << endl;
            }
            if(type == 2){
                cout << waza[r].first << endl;
            }
        }
}
0