#1185839 (C++23) No.3756 Udon Network

• 問題: No.3756 Udon Network
• ユーザー: tsunamayo123
• 提出日時: 2026-09-11 03:11:46
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 661 ms / 2,000 ms
• コード長: 3,888 bytes
• コンパイル時間: 4,270 ms
• コンパイル使用メモリ: 393,888 KB
• 実行使用メモリ: 68,436 KB
• 最終ジャッジ日時: 2026-10-09 17:32:44
• 合計ジャッジ時間: 29,183 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge2_0

サブタスク	配点	結果
Example	0 %	AC * 8
Subtask $1$	2 %	AC * 15
Subtask $2$	4 %	AC * 22
Subtask $3$	8 %	AC * 9
Subtask $4$	16 %	AC * 10
Subtask $5$	32 %	AC * 10
Subtask $6$	38 %	AC * 53
合計	4 * 100% = 400 点

ソースコード

// 部分点6(満点)
// Kruskal Reconstruction Tree + Euler Tour + BIT(fenwick tree) + Binary lifting

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;

int main(){
    int N,M,Q;
    cin>>N>>M>>Q;

    vector<int> A(N);
    for(int i=0; i<N; i++){
        cin>>A[i];
        A[i]--;
    }

    vector<pair<int,int>> B;

    vector<int> U(M),V(M),W(M);
    for(int j=0; j<M; j++){
        cin>>U[j]>>V[j]>>W[j];
        U[j]--,V[j]--;

        B.push_back({W[j],j});
    }
    sort(B.begin(),B.end());

    vector<pair<int,int>> child(2*N,{-1,-1});
    vector<int> parent(2*N,-1);
    vector<long long> weight(2*N,0);

    dsu UF(N);

    vector<int> comp(N);
    for(int i=0; i<N; i++)comp[i]=i;

    int nodes = N;

    // Kruskal Reconstruction Treeを構築してる
    for(auto [w,j]:B){
        int a=UF.leader(U[j]);
        int b=UF.leader(V[j]);

        if(a==b)continue;

        int x=comp[a];
        int y=comp[b];
        int z=nodes; nodes++;

        // 新しくwの頂点を作って、子にx,yを持たせる
        weight[z]=w;
        child[z]={x,y};

        parent[x]=parent[y]=z;

        int root=UF.merge(a,b);
        comp[root]=z;
    }
    int root=comp[UF.leader(0)];

    // DFSでEuler Tourを構築
    stack<int> st;
    st.push(root);

    vector<int> order;
    while(!st.empty()){
        int i=st.top();
        st.pop();

        if(i<N){
            order.push_back(i);
        }else{
            st.push(child[i].first);
            st.push(child[i].second);
        }
    }

    vector<int> L(nodes),R(nodes);
    for(int i=0; i<N; i++){
        int v=order[i];
        L[v]=R[v]=i; // 必ず葉なのでLとRは同じ
    }

    // rootに近づくほど頂点番号が大きくなってるので、小さい順に処理する
    for(int i=N; i<nodes; i++){
        auto [a,b]=child[i];
        L[i]=min(L[a],L[b]); // 頂点に入っていくとき
        R[i]=max(R[a],R[b]); // 頂点から出ていくとき
    }


    // BIT(fenwick tree)を用いて、ある頂点におけるEuler Tourの区間内の種類数を求める
    vector<int> last(N,-1);
    vector<int> cnt(nodes);

    fenwick_tree<int> fw(N);

    // R[i]が小さい順から見る -> 頂点から出ていく時間が早い順
    vector<vector<int>> r(N);
    for(int i=0; i<nodes; i++){
        r[R[i]].push_back(i);
    }

    for(int i=0; i<N; i++){
        int v=order[i];
        int c=A[v];

        // 種類数をsumで求めるために系列cの+1を移動する
        if(last[c]!=-1)fw.add(last[c],-1);
        fw.add(i,+1);
        last[c]=i; // 更新し忘れてた

        for(int u:r[i]){
            cnt[u]=fw.sum(L[u],R[u]+1);
        }
    }

    // s_kのcnt[v]>=c_kとなる祖先vがあるとき、weight[v]が答え
    // Binary lifting(ダブリング)を使ってvを求める
    int siz=1;
    while((1<<siz)<=nodes)siz++;

    vector<vector<int>> up(siz,vector<int>(nodes,-1));

    for(int v=0; v<nodes; v++)up[0][v]=parent[v]; // vの2^0個上の祖先はvの親
    for(int j=1; j<siz; j++){
        for(int v=0; v<nodes; v++){
            if(up[j-1][v]!=-1){
                up[j][v]=up[j-1][up[j-1][v]]; // ここダブリング
            }
        }
    }

    for(int k=0; k<Q; k++){
        int s,c;
        cin>>s>>c;
        s--;
        
        if(cnt[root]<c)cout<<-1<<endl; // CRTの根が最大値を取る
        else if(cnt[s]>=c)cout<<0<<endl;
        else{
            int v=s;
            for(int j=siz-1; 0<=j; j--){
                int x=up[j][v];
                // cnt[x]==cとなるギリギリまで祖先を登る(cntは単調増加)
                if(x!=-1 && cnt[x]<c){
                    v=x;
                }
            }
            int x=up[0][v]; // KRTで追加したw_jを持っている点
            cout<<weight[x]<<endl;
        }
    }
}