結果

問題 No.872 All Tree Path
ユーザー kafuka97
提出日時 2019-08-30 22:09:05
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 177 ms / 3,000 ms
コード長 3,162 bytes
コンパイル時間 1,894 ms
コンパイル使用メモリ 171,228 KB
実行使用メモリ 43,424 KB
最終ジャッジ日時 2024-11-21 23:50:46
合計ジャッジ時間 4,427 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
typedef int64_t i64;
typedef uint64_t ui64;
class graph{
public:
struct adj{
int index;
int start;
int to;
i64 cost;
};
int nd;
int eg;
vector<adj> *node;
vector<adj> edge;
graph(int n,int m){
nd=n;
eg=m;
node=new vector<adj>[nd]{};
edge={};
}
void add_dir(int i,int s,int t,i64 c){
node[s].push_back({i,s,t,c});
edge.push_back({i,s,t,c});
}
void add_undir(int i,int s,int t,i64 c){
node[s].push_back({i,s,t,c});
node[t].push_back({i,t,s,c});
edge.push_back({i,s,t,c});
}
void refr(void){
for(int i=0;i<nd;i++) vector<adj>().swap(node[i]);
delete[] node;
vector<adj>().swap(edge);
}
bool IsLink(void);
void DFS(int r,int *&p);
void DFS_sub(int r,int *&p,bool *&vst);
bool IsPlus(void);
void BellmanFord(int s,i64 *&d);
void Dijkstra(int s,i64 *&d);
void BFS(int s,i64 *&d);
void WarshallFloyd_dir(i64 **&d);
void WarshallFloyd_undir(i64 **&d);
i64 WMST_dir(int r);
i64 WMST_undir(void);
void Edmonds(int r,vector<adj> &p);
void Kruscal(vector<adj> &p);
void Prim(vector<adj> &p);
void Artic(vector<int> &p);
void Artic_sub(int r,int &k,int par,vector<int> &p,int *&ord,int *&low,bool *&vst);
void Bridge(vector<adj> &p);
void Bridge_sub(int r,int &k,int par,vector<adj> &p,int *&ord,int *&low,bool *&vst);
void SCC(int *&c);
void SCC_sub1(int r,vector<int> &vs,bool *&vst);
void SCC_sub2(int r,int k,int *&c,bool *&vst,graph &rg);
bool IsDAG(void);
bool IsDAG_sub(int r,int &k,int *&l,int *&vst);
void TopolSort(int *&l);
void TopolSort_sub(int r,int &k,int *&l,bool *&vst);
i64 Diameter(void);
void Height(i64 *&h);
void DFSTree(int s,vector<adj> &es);
void DFSTree_sub(int r,vector<adj> &es,bool *&vst);
void Cumul(int s,i64 *&d);
void func(int r,int *&p,i64 *&es);
void func_sub(int r,int *&p,i64 *&es,bool *&vst);
};
void graph::DFS(int r,int *&p){
bool *vst=new bool[nd]{};
DFS_sub(r,p,vst);
delete[] vst;
}
void graph::DFS_sub(int r,int *&p,bool *&vst){
vst[r]=1;
int c=0;
for(const auto &i:node[r]){
if(!vst[i.to]) DFS_sub(i.to,p,vst);
c+=p[i.to];
}
p[r]=c+1;
}
void graph::func(int r,int *&p,i64 *&es){
bool *vst=new bool[nd]{};
func_sub(r,p,es,vst);
delete[] vst;
}
void graph::func_sub(int r,int *&p,i64 *&es,bool *&vst){
vst[r]=1;
for(const auto &i:node[r]){
if(vst[i.to]) continue;
es[i.index]=(i64)p[i.to]*((i64)nd-p[i.to])*2;
func_sub(i.to,p,es,vst);
}
}
int main(void){
int n;
scanf("%i",&n);
graph g(n,n-1);
int s,t;
i64 w;
for(int i=0;i<n-1;i++){
scanf("%i%i%lli",&s,&t,&w);
s--;
t--;
g.add_undir(i,s,t,w);
}
int *p=new int[n]{};
g.DFS(0,p);
i64 *es=new i64[n-1]{};
g.func(0,p,es);
i64 ans=0;
for(int i=0;i<n-1;i++){
ans+=es[i]*g.edge[i].cost;
}
printf("%lli\n",ans);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0