// KALAM
# include<bits/stdc++.h>
using namespace std;
const int N = 200000 + 77;
struct Tree {
int n , tim = 1 , d[N] , up[N] , par[N] , sz[N] , st[N] , en[N] , who[N];
vector < int > adj[N];
void dfsSz(int v) {
sz[v] = 1;
for(int u : adj[v]) {
if(find(adj[u].begin() , adj[u].end() , v) != adj[u].end())
adj[u].erase(find(adj[u].begin() , adj[u].end() , v));
d[u] = d[v] + 1;
par[u] = v;
dfsSz(u);
sz[v] += sz[u];
}
}
void dfsHv(int v) {
who[tim] = v;
st[v] = tim ++;
sort(adj[v].begin() , adj[v].end() , [&](int x , int y) { return sz[x] > sz[y];});
int cnt = 0;
for(int u : adj[v]) {
up[u] = u;
if(cnt ++ == 0)
up[u] = up[v];
dfsHv(u);
}
en[v] = tim;
}
inline int GetLca(int v , int u) {
while(up[v] != up[u]) {
if(d[up[v]] < d[up[u]])
swap(v , u);
v = par[up[v]];
}
if(d[v] > d[u])
swap(v , u);
return v;
}
inline int GetPar(int v , int k) {
while(d[v] - d[up[v]] < k)
k -= d[v] - d[up[v]] + 1 , v = par[up[v]];
return who[st[v] - k];
}
inline int GetKth(int v , int u , int k) {
int Lca = GetLca(v , u);
if(k <= d[v] - d[Lca] + 1)
return GetPar(v , k - 1);
k -= d[v] - d[Lca] + 1;
return GetPar(u , d[u] - d[Lca] - k);
}
inline int GetDistance(int v , int u) {
return d[v] + d[u] - (d[GetLca(v , u)] << 1);
}
void BuildHLD(int root) {
for(int i = 0;i < N;++ i)
d[i] = st[i] = en[i] = sz[i] = par[i] = up[i] = who[i] = 0;
tim = 1;
up[root] = root;
dfsSz(root);
dfsHv(root);
}
} Tree;
long long A;
int n , Ev[N] , Eu[N] , C1[N] , C2[N] , dp[N];
vector < int > adj[N];
void dfs(int v , int prev = -1) {
for(int u : adj[v])
if(u != prev)
dfs(u , v) , dp[v] += dp[u];
}
int main() {
scanf("%d" , & n);
for(int i = 1;i < n;++ i) {
scanf("%d %d %d %d" , Ev + i , Eu + i , C1 + i , C2 + i);
Tree.adj[Ev[i]].push_back(Eu[i]);
Tree.adj[Eu[i]].push_back(Ev[i]);
adj[Ev[i]].push_back(Eu[i]);
adj[Eu[i]].push_back(Ev[i]);
}
Tree.BuildHLD(1);
for(int i = 1;i < n;++ i) {
int lca = Tree.GetLca(i , i + 1);
++ dp[i];++ dp[i + 1];
dp[lca] -= 2;
}
dfs(1);
for(int i = 1;i < n;++ i) {
if(Tree.d[Ev[i]] > Tree.d[Eu[i]])
swap(Ev[i] , Eu[i]);
if(dp[Eu[i]] * 1ll * C1[i] >= C2[i])
A += C2[i];
else
A += C1[i] * 1ll * dp[Eu[i]];
}
printf("%lld\n" , A);
return 0;
}
Compilation message
putovanje.cpp: In function 'int main()':
putovanje.cpp:78:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d" , & n);
~~~~~^~~~~~~~~~~~
putovanje.cpp:80:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d" , Ev + i , Eu + i , C1 + i , C2 + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
15232 KB |
Output is correct |
2 |
Correct |
14 ms |
15360 KB |
Output is correct |
3 |
Correct |
15 ms |
15360 KB |
Output is correct |
4 |
Correct |
15 ms |
15360 KB |
Output is correct |
5 |
Correct |
15 ms |
15360 KB |
Output is correct |
6 |
Correct |
15 ms |
15232 KB |
Output is correct |
7 |
Correct |
15 ms |
15232 KB |
Output is correct |
8 |
Correct |
14 ms |
15360 KB |
Output is correct |
9 |
Correct |
15 ms |
15360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
25976 KB |
Output is correct |
2 |
Correct |
114 ms |
26872 KB |
Output is correct |
3 |
Correct |
112 ms |
28152 KB |
Output is correct |
4 |
Correct |
139 ms |
30088 KB |
Output is correct |
5 |
Correct |
14 ms |
15360 KB |
Output is correct |
6 |
Correct |
107 ms |
27388 KB |
Output is correct |
7 |
Correct |
78 ms |
24312 KB |
Output is correct |
8 |
Correct |
114 ms |
27768 KB |
Output is correct |
9 |
Correct |
97 ms |
28228 KB |
Output is correct |
10 |
Correct |
86 ms |
27896 KB |
Output is correct |
11 |
Correct |
88 ms |
28920 KB |
Output is correct |
12 |
Correct |
96 ms |
29048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
15232 KB |
Output is correct |
2 |
Correct |
14 ms |
15360 KB |
Output is correct |
3 |
Correct |
15 ms |
15360 KB |
Output is correct |
4 |
Correct |
15 ms |
15360 KB |
Output is correct |
5 |
Correct |
15 ms |
15360 KB |
Output is correct |
6 |
Correct |
15 ms |
15232 KB |
Output is correct |
7 |
Correct |
15 ms |
15232 KB |
Output is correct |
8 |
Correct |
14 ms |
15360 KB |
Output is correct |
9 |
Correct |
15 ms |
15360 KB |
Output is correct |
10 |
Correct |
106 ms |
25976 KB |
Output is correct |
11 |
Correct |
114 ms |
26872 KB |
Output is correct |
12 |
Correct |
112 ms |
28152 KB |
Output is correct |
13 |
Correct |
139 ms |
30088 KB |
Output is correct |
14 |
Correct |
14 ms |
15360 KB |
Output is correct |
15 |
Correct |
107 ms |
27388 KB |
Output is correct |
16 |
Correct |
78 ms |
24312 KB |
Output is correct |
17 |
Correct |
114 ms |
27768 KB |
Output is correct |
18 |
Correct |
97 ms |
28228 KB |
Output is correct |
19 |
Correct |
86 ms |
27896 KB |
Output is correct |
20 |
Correct |
88 ms |
28920 KB |
Output is correct |
21 |
Correct |
96 ms |
29048 KB |
Output is correct |
22 |
Correct |
164 ms |
25596 KB |
Output is correct |
23 |
Correct |
127 ms |
24184 KB |
Output is correct |
24 |
Correct |
150 ms |
25192 KB |
Output is correct |
25 |
Correct |
15 ms |
15360 KB |
Output is correct |
26 |
Correct |
59 ms |
19704 KB |
Output is correct |
27 |
Correct |
138 ms |
24056 KB |
Output is correct |
28 |
Correct |
76 ms |
26488 KB |
Output is correct |
29 |
Correct |
90 ms |
29048 KB |
Output is correct |
30 |
Correct |
92 ms |
28792 KB |
Output is correct |
31 |
Correct |
14 ms |
15360 KB |
Output is correct |