ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211854 | #3807. 随机游走 | x_add_b | 100 | 926ms | 63684kb | C++11 | 1.3kb | 2024-10-07 16:20:43 | 2024-10-29 10:32:45 |
answer
#include<bits/stdc++.h>
namespace IO
{
template<typename Type>
void read(Type &x){
char ch=getchar();
x=0;bool f=0;
while(ch<'0'||ch>'9')
f|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')
x=((x<<1)+(x<<3)+(ch^48)),ch=getchar();
x=f?-x:x;
}
}
using namespace std;
#define N 500005
#define LL long long
int n,w;
int val[N],fa[N];
LL sigmaV[N],sigmaW[N];
LL nowtime,ans;
bool opt1=true,opt2=true;
struct node
{
int v,w;
bool operator < (const node &a) const
{
return 1ll*sigmaW[v]*sigmaV[a.v]<1ll*sigmaW[a.v]*sigmaV[v];
}
};
vector<node> Graph[N];
void dfs(int u)
{
ans+=(1ll*nowtime*val[u]);
for(int i=0;i<Graph[u].size();i++){
nowtime+=Graph[u][i].w;
dfs(Graph[u][i].v);
}
}
void initdfs(int u)
{
sigmaV[u]=val[u];
for(int i=0;i<Graph[u].size();i++){
int v=Graph[u][i].v,w=Graph[u][i].w;
sigmaW[v]+=w;
initdfs(v);
sigmaV[u]+=sigmaV[v];
sigmaW[u]+=sigmaW[v];
}
}
int main()
{
// freopen("ex_walk3.in","r",stdin);
IO::read(n);
for(int i=2;i<=n;i++){
IO::read(fa[i]);IO::read(w);
Graph[fa[i]].push_back({i,w});
}
for(int i=1;i<=n;i++)
IO::read(val[i]);
initdfs(1);
for(int i=1;i<=n;i++)
sort(Graph[i].begin(),Graph[i].end());
dfs(1);
printf("%lld",ans);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 3ms
memory: 12936kb
input:
11 1 653 2 978 3 277 4 562 3 119 6 957 3 362 6 637 6 157 9 939 460 270 127 466 193 710 45 318 281 74...
output:
11506132
result:
ok single line: '11506132'
Test #2:
score: 10
Accepted
time: 19ms
memory: 15872kb
input:
50000 1 983 1 937 2 776 4 753 2 494 2 683 2 335 4 316 7 274 6 638 11 535 10 872 13 808 13 817 11 94 ...
output:
276117269146880
result:
ok single line: '276117269146880'
Test #3:
score: 10
Accepted
time: 0ms
memory: 12972kb
input:
1000 1 729 1 239 1 433 1 445 1 877 1 648 1 284 1 814 1 287 1 941 1 183 1 126 1 65 1 500 1 823 1 725 ...
output:
94592611925
result:
ok single line: '94592611925'
Test #4:
score: 10
Accepted
time: 0ms
memory: 12976kb
input:
1000 1 790 1 229 1 462 1 658 1 880 1 507 1 109 1 66 1 356 1 477 1 963 1 689 1 284 1 962 1 896 1 671 ...
output:
91654782236
result:
ok single line: '91654782236'
Test #5:
score: 10
Accepted
time: 100ms
memory: 63684kb
input:
500000 1 87 2 160 3 87 4 518 5 214 6 654 7 329 8 614 9 590 10 13 11 546 12 35 13 417 14 304 15 884 1...
output:
31331837945244749
result:
ok single line: '31331837945244749'
Test #6:
score: 10
Accepted
time: 141ms
memory: 28480kb
input:
500000 1 697 1 11 1 698 1 189 1 824 1 524 1 163 1 335 1 959 1 690 1 368 1 168 1 673 1 398 1 918 1 42...
output:
16263658814895739
result:
ok single line: '16263658814895739'
Test #7:
score: 10
Accepted
time: 132ms
memory: 28480kb
input:
500000 1 148 1 159 1 990 1 585 1 837 1 364 1 754 1 576 1 756 1 426 1 502 1 201 1 185 1 251 1 17 1 20...
output:
16307730758229655
result:
ok single line: '16307730758229655'
Test #8:
score: 10
Accepted
time: 170ms
memory: 32092kb
input:
500000 1 252 1 377 1 130 4 779 5 531 4 815 2 176 4 514 9 21 9 142 2 72 11 293 11 579 9 870 7 731 9 3...
output:
48685536049668
result:
ok single line: '48685536049668'
Test #9:
score: 10
Accepted
time: 163ms
memory: 32108kb
input:
500000 1 484 1 48 3 523 2 793 4 822 1 622 3 874 4 54 6 568 4 867 11 500 7 974 4 966 7 793 1 140 1 40...
output:
49118321005585
result:
ok single line: '49118321005585'
Test #10:
score: 10
Accepted
time: 198ms
memory: 32112kb
input:
500000 1 456 2 231 2 525 4 823 2 377 1 72 2 644 5 391 1 984 1 996 7 590 4 604 7 359 3 138 4 843 3 22...
output:
21539113052010528
result:
ok single line: '21539113052010528'
Extra Test:
score: 0
Extra Test Passed