結果

問題 No.872 All Tree Path
ユーザー LayCurse
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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);
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0