#include <iostream>
#include <cmath>
#include <vector>
#include <utility>
using namespace std;
#define f first
#define s second
#define mp make_pair
int pred[21][200003],height[200003],parent[200003],n;
long long dp[21][200003];
vector<pair<int,pair<long long,long long> > > veki[200003];
pair<long long,long long> cijena[200003];
void dfs(int x,int p){
height[x]=height[p]+1;
parent[x]=p;
for(int i=0;i<veki[x].size();i++){
if(veki[x][i].f==p){
cijena[x]=veki[x][i].s;
continue;
}
dfs(veki[x][i].f,x);
}
}
void prep(){
for(int i=1;i<=n;i++){
pred[0][i]=parent[i];
}
for(int i=1;i<21;i++){
for(int j=1;j<=n;j++){
pred[i][j]=pred[i-1][pred[i-1][j]];
}
}
}
int getanc(int x,int v){
if(v==0) return x;
for(int i=0;i<21;i++){
if(v&(1<<i)){
dp[i][x]++;
x=pred[i][x];
}
}
return x;
}
void lca(int x,int y){
if(height[y]>height[x]) swap(x,y);
x=getanc(x,height[x]-height[y]);
if(x==y) return;
for(int i=20;i>=0;i--){
if(pred[i][x]==pred[i][y]) continue;
dp[i][x]++;
dp[i][y]++;
x=pred[i][x];
y=pred[i][y];
}
dp[0][x]++;
dp[0][y]++;
}
int main () {
cin>>n;
for(int i=0;i<n-1;i++){
long long c1,c2;
int a,b;
cin>>a>>b>>c1>>c2;
veki[a].push_back(mp(b,mp(c1,c2)));
veki[b].push_back(mp(a,mp(c1,c2)));
}
dfs(1,0);
prep();
for(int i=1;i<n;i++){
lca(i,i+1);
}
for(int i=20;i>0;i--){
for(int j=1;j<=n;j++){
dp[i-1][j]+=dp[i][j];
dp[i-1][pred[i-1][j]]+=dp[i][j];
}
}
long long sol=0;
for(int i=2;i<=n;i++){
sol+=min(dp[0][i]*cijena[i].f,cijena[i].s);
}
cout<<sol;
return 0;
}
Compilation message
putovanje.cpp: In function 'void dfs(int, int)':
putovanje.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<veki[x].size();i++){
~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
5240 KB |
Output is correct |
2 |
Correct |
11 ms |
5884 KB |
Output is correct |
3 |
Correct |
11 ms |
6008 KB |
Output is correct |
4 |
Correct |
12 ms |
6008 KB |
Output is correct |
5 |
Correct |
12 ms |
6008 KB |
Output is correct |
6 |
Correct |
8 ms |
5368 KB |
Output is correct |
7 |
Correct |
9 ms |
5496 KB |
Output is correct |
8 |
Correct |
10 ms |
5752 KB |
Output is correct |
9 |
Correct |
11 ms |
5880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
257 ms |
37240 KB |
Output is correct |
2 |
Correct |
264 ms |
40152 KB |
Output is correct |
3 |
Correct |
293 ms |
43768 KB |
Output is correct |
4 |
Correct |
315 ms |
44280 KB |
Output is correct |
5 |
Correct |
9 ms |
5496 KB |
Output is correct |
6 |
Correct |
259 ms |
38264 KB |
Output is correct |
7 |
Correct |
165 ms |
28892 KB |
Output is correct |
8 |
Correct |
277 ms |
39288 KB |
Output is correct |
9 |
Correct |
210 ms |
41464 KB |
Output is correct |
10 |
Correct |
207 ms |
40184 KB |
Output is correct |
11 |
Correct |
219 ms |
43228 KB |
Output is correct |
12 |
Correct |
232 ms |
43512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
5240 KB |
Output is correct |
2 |
Correct |
11 ms |
5884 KB |
Output is correct |
3 |
Correct |
11 ms |
6008 KB |
Output is correct |
4 |
Correct |
12 ms |
6008 KB |
Output is correct |
5 |
Correct |
12 ms |
6008 KB |
Output is correct |
6 |
Correct |
8 ms |
5368 KB |
Output is correct |
7 |
Correct |
9 ms |
5496 KB |
Output is correct |
8 |
Correct |
10 ms |
5752 KB |
Output is correct |
9 |
Correct |
11 ms |
5880 KB |
Output is correct |
10 |
Correct |
257 ms |
37240 KB |
Output is correct |
11 |
Correct |
264 ms |
40152 KB |
Output is correct |
12 |
Correct |
293 ms |
43768 KB |
Output is correct |
13 |
Correct |
315 ms |
44280 KB |
Output is correct |
14 |
Correct |
9 ms |
5496 KB |
Output is correct |
15 |
Correct |
259 ms |
38264 KB |
Output is correct |
16 |
Correct |
165 ms |
28892 KB |
Output is correct |
17 |
Correct |
277 ms |
39288 KB |
Output is correct |
18 |
Correct |
210 ms |
41464 KB |
Output is correct |
19 |
Correct |
207 ms |
40184 KB |
Output is correct |
20 |
Correct |
219 ms |
43228 KB |
Output is correct |
21 |
Correct |
232 ms |
43512 KB |
Output is correct |
22 |
Correct |
262 ms |
38904 KB |
Output is correct |
23 |
Correct |
219 ms |
35064 KB |
Output is correct |
24 |
Correct |
247 ms |
38348 KB |
Output is correct |
25 |
Correct |
10 ms |
5624 KB |
Output is correct |
26 |
Correct |
90 ms |
20472 KB |
Output is correct |
27 |
Correct |
208 ms |
33528 KB |
Output is correct |
28 |
Correct |
179 ms |
37112 KB |
Output is correct |
29 |
Correct |
228 ms |
43384 KB |
Output is correct |
30 |
Correct |
213 ms |
43000 KB |
Output is correct |
31 |
Correct |
10 ms |
5752 KB |
Output is correct |