結果
問題 | No.901 K-ary εxtrεεmε |
ユーザー |
![]() |
提出日時 | 2019-10-04 22:31:20 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 331 ms / 3,000 ms |
コード長 | 2,290 bytes |
コンパイル時間 | 1,416 ms |
コンパイル使用メモリ | 173,324 KB |
実行使用メモリ | 34,944 KB |
最終ジャッジ日時 | 2024-10-04 06:23:44 |
合計ジャッジ時間 | 8,599 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 29 |
コンパイルメッセージ
main.cpp: In function ‘void solve()’: main.cpp:75:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 75 | int K;scanf("%lld",&K); | ~~~~~^~~~~~~~~~~ main.cpp:76:33: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 76 | vint vs(K);rep(i,K)scanf("%lld",&vs[i]); | ~~~~~^~~~~~~~~~~~~~~ main.cpp: In function ‘int main()’: main.cpp:109:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 109 | scanf("%lld",&N); | ~~~~~^~~~~~~~~~~ main.cpp:112:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 112 | scanf("%lld%lld%lld",&a,&b,&c); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:125:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 125 | int Q;scanf("%lld",&Q); | ~~~~~^~~~~~~~~~~
ソースコード
#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; }