#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define int long long
using namespace std;
const int N=1e6,M=2e3,mod=1e9+7;
int n,up[N][30],innode[N],outnode[N],timee=0,val[N],val2[N];
map<pair<int,int>,int>mpp;
vector<int>adj[N];
vector<pair<int,int>>v;
void dfs(int node,int par){
innode[node]=timee++;
up[node][0]=par;
for(int j=1;j<ceil(log2(n));j++)
up[node][j]=up[up[node][j-1]][j-1];
for(auto x:adj[node]){
if(x==par)
continue;
dfs(x,node);
}
outnode[node]=timee++;
}
bool is_parent(int x,int y){
return innode[x]<=innode[y]&&outnode[x]>=outnode[y];
}
int lca(int x,int y){
if(is_parent(x,y))
return x;
if(is_parent(y,x))
return y;
for(int i=ceil(log2(n))+1;i>=0;i--){
if(!is_parent(up[x][i],y))
x=up[x][i];
}
return up[x][0];
}
void dfs2(int node,int par){
for(auto x:adj[node]){
if(x==par)
continue;
dfs2(x,node);
val2[node]+=val2[x];
mpp[{node,x}]=val2[x];
mpp[{x,node}]=val2[x];
}
val2[node]+=val[node];
}
main()
{
cin>>n;
map<pair<int,int>,pair<int,int>>mp;
for(int i=0;i<n-1;i++){
int x,y,cost1,cost2;
cin>>x>>y>>cost1>>cost2;
v.pb({x,y});
mp[{x,y}]={cost1,cost2};
adj[x].pb(y);
adj[y].pb(x);
}
dfs(1,0);
innode[0]=-1;
outnode[0]=++timee;
for(int i=2;i<=n;i++){
int lcaa=lca(i,i-1);
val[i]++;
val[i-1]++;
val[lcaa]-=2;
}
dfs2(1,0);
int ans=0;
for(int i=0;i<v.size();i++){
int cost1=mp[{v[i].F,v[i].S}].F*mpp[{v[i].F,v[i].S}];
int cost2=mp[{v[i].F,v[i].S}].S;
ans+=min(cost1,cost2);
}
cout<<ans<<endl;
return 0;
}
Compilation message
putovanje.cpp:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
74 | main()
| ^~~~
putovanje.cpp: In function 'int main()':
putovanje.cpp:112:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int i=0;i<v.size();i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
17 ms |
24660 KB |
Output is correct |
3 |
Correct |
18 ms |
24828 KB |
Output is correct |
4 |
Correct |
19 ms |
24888 KB |
Output is correct |
5 |
Correct |
19 ms |
24916 KB |
Output is correct |
6 |
Correct |
14 ms |
23892 KB |
Output is correct |
7 |
Correct |
14 ms |
24020 KB |
Output is correct |
8 |
Correct |
16 ms |
24448 KB |
Output is correct |
9 |
Correct |
19 ms |
24748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
399 ms |
78192 KB |
Output is correct |
2 |
Correct |
420 ms |
81236 KB |
Output is correct |
3 |
Correct |
452 ms |
87164 KB |
Output is correct |
4 |
Correct |
481 ms |
87616 KB |
Output is correct |
5 |
Correct |
15 ms |
24228 KB |
Output is correct |
6 |
Correct |
428 ms |
77236 KB |
Output is correct |
7 |
Correct |
254 ms |
62540 KB |
Output is correct |
8 |
Correct |
405 ms |
78972 KB |
Output is correct |
9 |
Correct |
278 ms |
81944 KB |
Output is correct |
10 |
Correct |
280 ms |
80152 KB |
Output is correct |
11 |
Correct |
295 ms |
84792 KB |
Output is correct |
12 |
Correct |
285 ms |
84964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
17 ms |
24660 KB |
Output is correct |
3 |
Correct |
18 ms |
24828 KB |
Output is correct |
4 |
Correct |
19 ms |
24888 KB |
Output is correct |
5 |
Correct |
19 ms |
24916 KB |
Output is correct |
6 |
Correct |
14 ms |
23892 KB |
Output is correct |
7 |
Correct |
14 ms |
24020 KB |
Output is correct |
8 |
Correct |
16 ms |
24448 KB |
Output is correct |
9 |
Correct |
19 ms |
24748 KB |
Output is correct |
10 |
Correct |
399 ms |
78192 KB |
Output is correct |
11 |
Correct |
420 ms |
81236 KB |
Output is correct |
12 |
Correct |
452 ms |
87164 KB |
Output is correct |
13 |
Correct |
481 ms |
87616 KB |
Output is correct |
14 |
Correct |
15 ms |
24228 KB |
Output is correct |
15 |
Correct |
428 ms |
77236 KB |
Output is correct |
16 |
Correct |
254 ms |
62540 KB |
Output is correct |
17 |
Correct |
405 ms |
78972 KB |
Output is correct |
18 |
Correct |
278 ms |
81944 KB |
Output is correct |
19 |
Correct |
280 ms |
80152 KB |
Output is correct |
20 |
Correct |
295 ms |
84792 KB |
Output is correct |
21 |
Correct |
285 ms |
84964 KB |
Output is correct |
22 |
Correct |
513 ms |
76356 KB |
Output is correct |
23 |
Correct |
430 ms |
70072 KB |
Output is correct |
24 |
Correct |
507 ms |
75504 KB |
Output is correct |
25 |
Correct |
15 ms |
24320 KB |
Output is correct |
26 |
Correct |
212 ms |
47696 KB |
Output is correct |
27 |
Correct |
445 ms |
67916 KB |
Output is correct |
28 |
Correct |
240 ms |
75192 KB |
Output is correct |
29 |
Correct |
325 ms |
85128 KB |
Output is correct |
30 |
Correct |
289 ms |
84492 KB |
Output is correct |
31 |
Correct |
16 ms |
24660 KB |
Output is correct |