結果
問題 | 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 |
コンパイル時間 | 2,114 ms |
コンパイル使用メモリ | 172,656 KB |
実行使用メモリ | 36,664 KB |
最終ジャッジ日時 | 2024-04-15 00:11:25 |
合計ジャッジ時間 | 10,201 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 263 ms
36,664 KB |
testcase_01 | AC | 7 ms
22,600 KB |
testcase_02 | AC | 9 ms
24,764 KB |
testcase_03 | AC | 10 ms
22,728 KB |
testcase_04 | AC | 10 ms
24,644 KB |
testcase_05 | AC | 10 ms
24,772 KB |
testcase_06 | AC | 9 ms
22,860 KB |
testcase_07 | AC | 252 ms
32,276 KB |
testcase_08 | AC | 246 ms
32,620 KB |
testcase_09 | AC | 236 ms
32,716 KB |
testcase_10 | AC | 240 ms
32,584 KB |
testcase_11 | AC | 248 ms
32,356 KB |
testcase_12 | AC | 282 ms
32,416 KB |
testcase_13 | AC | 285 ms
32,544 KB |
testcase_14 | AC | 276 ms
32,392 KB |
testcase_15 | AC | 283 ms
32,436 KB |
testcase_16 | AC | 290 ms
32,440 KB |
testcase_17 | AC | 415 ms
32,476 KB |
testcase_18 | AC | 377 ms
32,668 KB |
testcase_19 | AC | 400 ms
32,320 KB |
testcase_20 | AC | 384 ms
32,520 KB |
testcase_21 | AC | 365 ms
32,604 KB |
testcase_22 | AC | 320 ms
32,844 KB |
testcase_23 | AC | 322 ms
32,972 KB |
testcase_24 | AC | 320 ms
33,200 KB |
testcase_25 | AC | 321 ms
33,200 KB |
testcase_26 | AC | 321 ms
33,340 KB |
testcase_27 | AC | 125 ms
32,456 KB |
testcase_28 | AC | 126 ms
32,320 KB |
testcase_29 | AC | 121 ms
32,208 KB |
コンパイルメッセージ
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; }