#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
struct Edge{
ll cost[2];
int to;
Edge(){}
Edge(int a,int b,int c){
to = a,cost[0] = b,cost[1] = c;
}
};
const int mxn = 2e5+10;
vector<Edge> tree[mxn];
ll bit[mxn];
pll val[mxn];
ll add[mxn],del[mxn];
int dep[mxn],idx[mxn],link_top[mxn],sz[mxn],par[mxn],bs[mxn],cnt;
int n;
void modify(int p,int v){
for(;p<mxn;p+=p&-p)bit[p] += v;
return;
}
ll getval(int p){
ll re= 0;
for(;p>0;p-= p&-p)re += bit[p];
return re;
}
void dfs1(int now){
sz[now] = 1;
for(auto nxt:tree[now]){
if(nxt.to == par[now])continue;
par[nxt.to] = now;
dep[nxt.to] = dep[now]+1;
val[nxt.to] = {nxt.cost[0],nxt.cost[1]};
dfs1(nxt.to);
if(!bs[now]||sz[bs[now]]<sz[nxt.to])bs[now] = nxt.to;
sz[now] += sz[nxt.to];
}
return;
}
void dfs2(int now,int top){
link_top[now] = top;
idx[now] = ++cnt;
if(bs[now])dfs2(bs[now],top);
for(auto nxt:tree[now]){
if(nxt.to == bs[now]||nxt.to == par[now])continue;
dfs2(nxt.to,nxt.to);
}
return;
}
void addval(int a,int b,int c){
int ta = link_top[a],tb = link_top[b];
while(ta != tb){
if(dep[ta]<dep[tb]){
swap(ta,tb);
swap(a,b);
}
modify(idx[ta],c);
modify(idx[a]+1,-c);
a = par[ta];ta = link_top[a];
}
if(dep[a]>dep[b])swap(a,b);
if(a != b){
modify(idx[a]+1,c);
modify(idx[b]+1,-c);
}
return;
}
main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i = 1;i<n;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
tree[a].push_back(Edge(b,c,d));
tree[b].push_back(Edge(a,c,d));
}
par[1] = 0;
dep[1] = 1;
dfs1(1);
dfs2(1,1);
for(int i = 2;i<=n;i++){
addval(i-1,i,1);
}
ll ans = 0;
for(int i = 2;i<=n;i++){
ans += min(getval(idx[i])*val[i].fs,val[i].sc);
}
cout<<ans;
}
Compilation message
putovanje.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
83 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18012 KB |
Output is correct |
2 |
Correct |
5 ms |
18012 KB |
Output is correct |
3 |
Correct |
4 ms |
18112 KB |
Output is correct |
4 |
Correct |
5 ms |
18264 KB |
Output is correct |
5 |
Correct |
4 ms |
18264 KB |
Output is correct |
6 |
Correct |
3 ms |
18012 KB |
Output is correct |
7 |
Correct |
4 ms |
18012 KB |
Output is correct |
8 |
Correct |
4 ms |
18084 KB |
Output is correct |
9 |
Correct |
4 ms |
18012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
29412 KB |
Output is correct |
2 |
Correct |
49 ms |
30260 KB |
Output is correct |
3 |
Correct |
56 ms |
31212 KB |
Output is correct |
4 |
Correct |
59 ms |
30804 KB |
Output is correct |
5 |
Correct |
3 ms |
18012 KB |
Output is correct |
6 |
Correct |
49 ms |
29020 KB |
Output is correct |
7 |
Correct |
31 ms |
24920 KB |
Output is correct |
8 |
Correct |
52 ms |
31060 KB |
Output is correct |
9 |
Correct |
52 ms |
31312 KB |
Output is correct |
10 |
Correct |
49 ms |
30968 KB |
Output is correct |
11 |
Correct |
55 ms |
31828 KB |
Output is correct |
12 |
Correct |
56 ms |
32052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18012 KB |
Output is correct |
2 |
Correct |
5 ms |
18012 KB |
Output is correct |
3 |
Correct |
4 ms |
18112 KB |
Output is correct |
4 |
Correct |
5 ms |
18264 KB |
Output is correct |
5 |
Correct |
4 ms |
18264 KB |
Output is correct |
6 |
Correct |
3 ms |
18012 KB |
Output is correct |
7 |
Correct |
4 ms |
18012 KB |
Output is correct |
8 |
Correct |
4 ms |
18084 KB |
Output is correct |
9 |
Correct |
4 ms |
18012 KB |
Output is correct |
10 |
Correct |
60 ms |
29412 KB |
Output is correct |
11 |
Correct |
49 ms |
30260 KB |
Output is correct |
12 |
Correct |
56 ms |
31212 KB |
Output is correct |
13 |
Correct |
59 ms |
30804 KB |
Output is correct |
14 |
Correct |
3 ms |
18012 KB |
Output is correct |
15 |
Correct |
49 ms |
29020 KB |
Output is correct |
16 |
Correct |
31 ms |
24920 KB |
Output is correct |
17 |
Correct |
52 ms |
31060 KB |
Output is correct |
18 |
Correct |
52 ms |
31312 KB |
Output is correct |
19 |
Correct |
49 ms |
30968 KB |
Output is correct |
20 |
Correct |
55 ms |
31828 KB |
Output is correct |
21 |
Correct |
56 ms |
32052 KB |
Output is correct |
22 |
Correct |
104 ms |
28940 KB |
Output is correct |
23 |
Correct |
78 ms |
27668 KB |
Output is correct |
24 |
Correct |
85 ms |
28240 KB |
Output is correct |
25 |
Correct |
4 ms |
18012 KB |
Output is correct |
26 |
Correct |
37 ms |
21844 KB |
Output is correct |
27 |
Correct |
73 ms |
27216 KB |
Output is correct |
28 |
Correct |
43 ms |
29896 KB |
Output is correct |
29 |
Correct |
56 ms |
32084 KB |
Output is correct |
30 |
Correct |
57 ms |
31780 KB |
Output is correct |
31 |
Correct |
3 ms |
18012 KB |
Output is correct |