結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2019-08-30 21:27:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 55 ms / 3,000 ms |
コード長 | 3,469 bytes |
コンパイル時間 | 2,733 ms |
コンパイル使用メモリ | 211,804 KB |
最終ジャッジ日時 | 2025-01-07 15:44:36 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;void *wmem;template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){static int skip[16]={0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );(*arr)=(T*)(*mem);(*mem)=((*arr)+x);}inline void rd(int &x){int k, m=0;x=0;for(;;){k = getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}inline void wt_L(char a){putchar_unlocked(a);}inline void wt_L(long long x){char f[20];int m=0, s=0;if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){putchar_unlocked('-');}while(s--){putchar_unlocked(f[s]+'0');}}struct graph{int N, **edge, *es;void setEdge(int N__, int M, int A[], int B[], void **mem = &wmem){int i;N = N__;walloc1d(&es, N, mem);walloc1d(&edge, N, mem);for(i=0;i<(N);i++){es[i] = 0;}for(i=0;i<(M);i++){es[A[i]]++;es[B[i]]++;}for(i=0;i<(N);i++){walloc1d(&edge[i], es[i], mem);}for(i=0;i<(N);i++){es[i] = 0;}for(i=0;i<(M);i++){edge[A[i]][es[A[i]]++] = B[i];edge[B[i]][es[B[i]]++] = A[i];}}};template<class T> struct wgraph{T **cost;graph g;int N, **edge, *es;void setEdge(int N__, int M, int A[], int B[], T C[], void **mem = &wmem){int i;N = N__;walloc1d(&es, N, mem);for(i=0;i<(N);i++){es[i] = 0;}for(i=0;i<(M);i++){es[A[i]]++;es[B[i]]++;}walloc1d(&edge, N, mem);for(i=0;i<(N);i++){walloc1d(&edge[i], es[i], mem);}walloc1d(&cost, N, mem);for(i=0;i<(N);i++){walloc1d(&cost[i], es[i], mem);}for(i=0;i<(N);i++){es[i] = 0;}for(i=0;i<(M);i++){edge[A[i]][es[A[i]]] = B[i];edge[B[i]][es[B[i]]] = A[i];cost[A[i]][es[A[i]]++] = C[i];cost[B[i]][es[B[i]]++] = C[i];}g.N = N;g.es = es;g.edge = edge;}};char memarr[96000000];int N;int A[200000];int B[200000];int C[200000];wgraph<int> g;int cnt[200000];long long res;int dfs(int n, int b){int i, k, r=1, tmp;for(i=0;i<(g.es[n]);i++){k = g.edge[n][i];if(k==b){continue;}r += (tmp = dfs(k, n));res += (long long)2 * tmp * (N-tmp) * g.cost[n][i];}return r;}int main(){wmem = memarr;rd(N);{int Lj4PdHRW;for(Lj4PdHRW=0;Lj4PdHRW<(N-1);Lj4PdHRW++){rd(A[Lj4PdHRW]);A[Lj4PdHRW] += (-1);rd(B[Lj4PdHRW]);B[Lj4PdHRW] += (-1);rd(C[Lj4PdHRW]);}}g.setEdge(N,N-1,A,B,C);dfs(0, -1);wt_L(res);wt_L('\n');return 0;}// cLay varsion 20190830-1// --- original code ---// int N, A[2d5], B[2d5], C[2d5];// wgraph<int> g;//// int cnt[2d5];// ll res;//// int dfs(int n, int b){// int i, k;// int r = 1, tmp;//// rep(i,g.es[n]){// k = g.edge[n][i];// if(k==b) continue;// r += (tmp = dfs(k, n));// res += (ll)2 * tmp * (N-tmp) * g.cost[n][i];// }//// return r;// }//// {// rd(N,(A--,B--,C)(N-1));// g.setEdge(N,N-1,A,B,C);// dfs(0, -1);// wt(res);// }