結果

問題 No.901 K-ary εxtrεεmε
ユーザー latte0119
提出日時 2019-10-05 01:22:04
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 383 ms / 3,000 ms
コード長 3,411 bytes
コンパイル時間 1,668 ms
コンパイル使用メモリ 183,736 KB
実行使用メモリ 36,124 KB
最終ジャッジ日時 2024-10-04 06:30:03
合計ジャッジ時間 9,656 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:140:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  140 |         int K;scanf("%lld",&K);
      |               ~~~~~^~~~~~~~~~~
main.cpp:141:33: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  141 |         vint vs(K);rep(i,K)scanf("%lld",&vs[i]);
      |                            ~~~~~^~~~~~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:174:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  174 |         int N;scanf("%lld",&N);
      |               ~~~~~^~~~~~~~~~~
main.cpp:178:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  178 |                 scanf("%lld%lld%lld",&a,&b,&c);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:184:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  184 |         int Q;scanf("%lld",&Q);
      |               ~~~~~^~~~~~~~~~~

ソースコード

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

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<class W,int lg=1>
struct WeightedTree{
    struct Edge{
        int to;
        W cost;
        Edge(int to,W cost):to(to),cost(cost){}
    };
    int V;
    vector<vector<Edge>>G;
    vector<vector<int>>par;
    vector<int>dep,sz,head;
    vector<int>tin,tout;
    vector<W>dist;
    WeightedTree(int V=0):V(V),G(V),par(lg,vector<int>(V)),sz(V),dep(V),head(V),dist(V),tin(V),tout(V){}
    void addEdge(int a,int b,W c=W(1)){
        G[a].push_back(Edge(b,c));
        G[b].push_back(Edge(a,c));
    }
    void dfs(int v,int p,int d,W c){
        par[0][v]=p;
        dep[v]=d;
        sz[v]=1;
        dist[v]=c;
        for(auto &e:G[v]){
            if(e.to==p)continue;
            dfs(e.to,v,d+1,c+e.cost);
            sz[v]+=sz[e.to];
            if(G[v][0].to==p||sz[e.to]>sz[G[v][0].to])swap(G[v][0],e);
        }
    }
    void dfs_hld(int v,int &tt){
        tin[v]=tt++;
        for(auto &e:G[v]){
            if(e.to==par[0][v])continue;
            head[e.to]=(e.to==G[v][0].to)?head[v]:e.to;
            dfs_hld(e.to,tt);
        }
        tout[v]=tt;
    }
    void init(){
        dfs(0,-1,0,W(0));
        int tt=0;
        dfs_hld(0,tt);
        for(int i=0;i+1<lg;i++){
            for(int j=0;j<V;j++){
                if(par[i][j]==-1)par[i+1][j]=-1;
                else par[i+1][j]=par[i][par[i][j]];
            }
        }
    }
    // 1<<lg >=N-1!!!!!
    int getLCA(int u,int v){
        
        if(dep[u]<dep[v])swap(u,v);
        rep(i,lg)if((dep[u]-dep[v])>>i&1)u=par[i][u];
        if(u==v)return u;
        for(int i=lg-1;i>=0;i--)if(par[i][u]!=par[i][v])u=par[i][u],v=par[i][v];
        return par[0][v];
    }
    int getLength(int a,int b=0){
        int l=getLCA(a,b);
        return dep[a]+dep[b]-2*dep[l];
    }
    W getDistance(int a,int b=0){
        int l=getLCA(a,b);
        return dist[a]+dist[b]-2*dist[l];
    }
    int getParent(int v,int k=0){
        return par[k][v];
    }
    int getDepth(int v){
        return dep[v];
    }
    int getIn(int v){
        return tin[v];
    }
    int getOut(int v){
        return tout[v];
    }
};
/*
0-indexed
add(k,x): a[k]+=x
sum(k): sum(a[0,k])
space:O(N)
time:O(logN) per query
*/
struct BinaryIndexedTree{
    int n;
    vector<int>dat;
    BinaryIndexedTree(int n=0):n(n){
        dat.resize(n+1);
    }
    void add(int k,int x){
        for(k++;k<=n;k+=k&-k)dat[k]+=x;
    }
    int sum(int k){
        int ret=0;
        for(k++;k;k-=k&-k)ret+=dat[k];
        return ret;
    }
};
WeightedTree<int,20>T;
BinaryIndexedTree bit(111111);
void solve(){
    int K;scanf("%lld",&K);
    vint vs(K);rep(i,K)scanf("%lld",&vs[i]);
    set<pint>s;
    rep(i,K){
        s.insert({T.getDepth(vs[i]),vs[i]});
        bit.add(T.getIn(vs[i]),1);
    }
    int ans=0;
    
    
    
    while(s.size()>1){
        int v=s.rbegin()->se;
        s.erase(*s.rbegin());
        bit.add(T.getIn(v),-1);
        int u=v;
        for(int i=19;i>=0;i--){
            if(T.getParent(u,i)==-1)continue;
            int w=T.getParent(u,i);
            if(bit.sum(T.getOut(w)-1)-bit.sum(T.getIn(w)-1)==0){
                u=w;
            }
        }
        u=T.getParent(u);
        ans+=T.getDistance(u,v);
        if(s.find(pint(T.getDepth(u),u))!=s.end())continue;
        bit.add(T.getIn(u),1);
        s.insert(pint(T.getDepth(u),u));
    }
    printf("%lld\n",ans);
}
signed main(){
    int N;scanf("%lld",&N);
    T=WeightedTree<int,20>(N);
    rep(i,N-1){
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        T.addEdge(a,b,c);
    }
    T.init();
    int Q;scanf("%lld",&Q);
    while(Q--){
        solve();
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0