結果
問題 | No.901 K-ary εxtrεεmε |
ユーザー | 👑 kmjp |
提出日時 | 2019-10-05 00:39:35 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 292 ms / 3,000 ms |
コード長 | 2,178 bytes |
コンパイル時間 | 1,888 ms |
コンパイル使用メモリ | 173,364 KB |
実行使用メモリ | 34,004 KB |
最終ジャッジ日時 | 2024-04-15 00:13:52 |
合計ジャッジ時間 | 8,840 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 79 ms
34,004 KB |
testcase_01 | AC | 8 ms
26,664 KB |
testcase_02 | AC | 9 ms
27,772 KB |
testcase_03 | AC | 9 ms
27,048 KB |
testcase_04 | AC | 10 ms
27,896 KB |
testcase_05 | AC | 10 ms
27,400 KB |
testcase_06 | AC | 10 ms
28,176 KB |
testcase_07 | AC | 224 ms
31,408 KB |
testcase_08 | AC | 226 ms
31,904 KB |
testcase_09 | AC | 211 ms
31,908 KB |
testcase_10 | AC | 203 ms
31,812 KB |
testcase_11 | AC | 217 ms
31,772 KB |
testcase_12 | AC | 203 ms
30,700 KB |
testcase_13 | AC | 220 ms
32,036 KB |
testcase_14 | AC | 197 ms
31,984 KB |
testcase_15 | AC | 211 ms
30,508 KB |
testcase_16 | AC | 222 ms
31,904 KB |
testcase_17 | AC | 258 ms
31,724 KB |
testcase_18 | AC | 245 ms
32,304 KB |
testcase_19 | AC | 268 ms
31,904 KB |
testcase_20 | AC | 292 ms
31,908 KB |
testcase_21 | AC | 260 ms
31,704 KB |
testcase_22 | AC | 253 ms
30,668 KB |
testcase_23 | AC | 232 ms
32,104 KB |
testcase_24 | AC | 243 ms
30,648 KB |
testcase_25 | AC | 220 ms
30,812 KB |
testcase_26 | AC | 219 ms
30,508 KB |
testcase_27 | AC | 228 ms
32,432 KB |
testcase_28 | AC | 229 ms
31,516 KB |
testcase_29 | AC | 218 ms
32,032 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- int N,Q; vector<pair<int,int>> E[200005]; int P[21][200005],D[200005]; ll TD[200005]; int L[202020],R[202020],id; void dfs(int cur,int pre,ll tot) { TD[cur]=tot; P[0][cur]=pre; L[cur]=id++; FORR(e,E[cur]) if(e.first!=pre) D[e.first]=D[cur]+1, dfs(e.first,cur,tot+e.second); R[cur]=id; } int getpar(int cur,int up) { int i; FOR(i,20) if(up&(1<<i)) cur=P[i][cur]; return cur; } int lca(int a,int b) { int ret=0,i,aa=a,bb=b; if(D[aa]>D[bb]) swap(aa,bb); for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb]; for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb]; return (aa==bb)?aa:P[0][aa]; // vertex } int dist(int a,int b) { int ret=0,i,aa=a,bb=b; if(D[aa]>D[bb]) swap(aa,bb); for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb]; for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb]; return D[a]+D[b]-2*D[(aa==bb)?aa:P[0][aa]]; // dist } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N-1) { cin>>x>>y>>r; E[x].push_back({y,r}); E[y].push_back({x,r}); } dfs(0,0,0); FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]]; cin>>Q; while(Q--) { vector<pair<int,int>> V; cin>>x; FOR(i,x) { cin>>y; V.push_back({L[y],y}); } sort(ALL(V)); ll tot=0; int a=V[0].second, b=V[0].second; for(i=1;i<V.size();i++) { int c=V[i].second; int lc=lca(b,c); if(D[lc]<D[a]) { tot+=TD[a]-TD[lc]+TD[c]-TD[lc]; a=lc; } else { tot+=TD[c]-TD[lc]; } b=c; } cout<<tot<<endl; } } int main(int argc,char** argv){ string s;int i; if(argc==1) ios::sync_with_stdio(false), cin.tie(0); FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin); cout.tie(0); solve(); return 0; }