結果
問題 | No.901 K-ary εxtrεεmε |
ユーザー | latte0119 |
提出日時 | 2019-10-04 22:31:20 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 415 ms / 3,000 ms |
コード長 | 2,290 bytes |
コンパイル時間 | 3,067 ms |
コンパイル使用メモリ | 158,452 KB |
実行使用メモリ | 36,556 KB |
最終ジャッジ日時 | 2023-07-27 11:58:29 |
合計ジャッジ時間 | 10,356 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 267 ms
36,556 KB |
testcase_01 | AC | 7 ms
24,676 KB |
testcase_02 | AC | 10 ms
24,824 KB |
testcase_03 | AC | 10 ms
24,596 KB |
testcase_04 | AC | 10 ms
24,632 KB |
testcase_05 | AC | 10 ms
24,624 KB |
testcase_06 | AC | 10 ms
24,592 KB |
testcase_07 | AC | 255 ms
32,252 KB |
testcase_08 | AC | 240 ms
32,460 KB |
testcase_09 | AC | 221 ms
32,200 KB |
testcase_10 | AC | 235 ms
32,188 KB |
testcase_11 | AC | 241 ms
32,336 KB |
testcase_12 | AC | 277 ms
32,196 KB |
testcase_13 | AC | 279 ms
32,480 KB |
testcase_14 | AC | 278 ms
32,260 KB |
testcase_15 | AC | 282 ms
32,456 KB |
testcase_16 | AC | 273 ms
32,488 KB |
testcase_17 | AC | 415 ms
32,312 KB |
testcase_18 | AC | 381 ms
32,140 KB |
testcase_19 | AC | 395 ms
32,188 KB |
testcase_20 | AC | 381 ms
32,140 KB |
testcase_21 | AC | 364 ms
32,280 KB |
testcase_22 | AC | 306 ms
32,912 KB |
testcase_23 | AC | 300 ms
33,060 KB |
testcase_24 | AC | 316 ms
33,384 KB |
testcase_25 | AC | 301 ms
33,376 KB |
testcase_26 | AC | 295 ms
32,916 KB |
testcase_27 | AC | 115 ms
32,140 KB |
testcase_28 | AC | 117 ms
32,200 KB |
testcase_29 | AC | 118 ms
32,300 KB |
ソースコード
#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;} int N; int par[20][111111]; vector<pint>G[111111]; int dep[111111],cost[111111]; int tt,tin[111111],tout[111111]; void dfs(int v,int p,int d,int c){ tin[v]=tt++; dep[v]=d; par[0][v]=p; cost[v]=c; for(auto e:G[v]){ if(e.fi==p)continue; dfs(e.fi,v,d+1,c+e.se); } tout[v]=tt; } int lca(int u,int v){ if(dep[u]<dep[v])swap(u,v); rep(i,20)if((dep[u]-dep[v])>>i&1)u=par[i][u]; if(u==v)return u; for(int i=19;i>=0;i--)if(par[i][u]!=par[i][v])u=par[i][u],v=par[i][v]; return par[0][u]; } inline int calc(int x,int y){ int l=lca(x,y); return cost[x]+cost[y]-2*cost[l]; } /* 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; } }; 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({dep[vs[i]],vs[i]}); bit.add(tin[vs[i]],1); } int ans=0; while(s.size()>1){ int v=s.rbegin()->se; s.erase(*s.rbegin()); bit.add(tin[v],-1); int u=v; for(int i=19;i>=0;i--){ if(par[i][u]==-1)continue; int w=par[i][u]; if(bit.sum(tout[w]-1)-bit.sum(tin[w]-1)==0){ u=w; } } u=par[0][u]; ans+=calc(u,v); if(s.find(pint(dep[u],u))!=s.end())continue; bit.add(tin[u],1); s.insert(pint(dep[u],u)); } printf("%lld\n",ans); } signed main(){ scanf("%lld",&N); rep(i,N-1){ int a,b,c; scanf("%lld%lld%lld",&a,&b,&c); G[a].pb({b,c}); G[b].pb({a,c}); } dfs(0,-1,0,0); rep(i,19){ rep(j,N){ if(par[i][j]==-1)par[i+1][j]=-1; else par[i+1][j]=par[i][par[i][j]]; } } int Q;scanf("%lld",&Q); while(Q--){ solve(); } return 0; }