///Heavy Light Decomposition
///Problem: cowland (USACO)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int n,q;
int p[N], d[N], sz[N], h[N], pos[N], e[N];
int fw[N];
int A[N], B[N], C1[N], C2[N];
int v1[N], v2[N];
int ct = 1;
vector<int> adjlist[N];
void up(int x, int v){
while (x < N){
fw[x] += v;
x += x&(-x);
}
}
int query(int x){
int res = 0;
while (x){
res += fw[x];
x -= x&(-x);
}
return res;
}
void rangeadd(int s, int e){
up(s,1);
up(e+1,-1);
}
void dfs(int u){
sz[u] = 1;
for (auto v : adjlist[u]){
if (p[v] == 0){
p[v] = u;
d[v] = d[u]+1;
dfs(v);
sz[u] += sz[v];
}
}
}
void decomp(int u){
pos[u] = ct++;
int heavy = 0;
for (auto v : adjlist[u]){
if (p[u] == v) continue;
if (sz[heavy] < sz[v]) heavy = v;
}
if (heavy == 0) return;
h[heavy] = h[u];
decomp(heavy);
for (auto v : adjlist[u]){
if (v != heavy && v != p[u]) decomp(v);
}
}
void add(int u, int v){
//printf("adding on path %d->%d\n",u,v);
int ans = 0;
while (h[u] != h[v]){
if (u == 0 || v == 0) break;;
//printf("%d,%d\n",u,v);
if (d[h[u]] > d[h[v]]) swap(u,v);
//printf("moving from %d -> %d\n",pos[v],pos[h[v]]);
rangeadd(pos[h[v]],pos[v]);
v = p[h[v]];
}
if (d[u] > d[v]) swap(u,v);
//printf("cur at %d %d\n",pos[u],pos[v]);
rangeadd(pos[u]+1,pos[v]);
}
/*
int que(int u, int v){
int ans = 0;
while (h[u] != h[v]){
if (u == 0 || v == 0) return 0;
if (d[h[u]] > d[h[v]]) swap(u,v);
ans ^= root->query(pos[h[v]],pos[v]);
v = p[h[v]];
}
if (d[u] > d[v]) swap(u,v);
ans ^= root->query(pos[u],pos[v]);
return ans;
}*/
int main(){
scanf("%d",&n);
for (int i = 1; i < n; i++){
scanf("%d%d%d%d",&A[i],&B[i],&C1[i],&C2[i]);
adjlist[A[i]].push_back(B[i]);
adjlist[B[i]].push_back(A[i]);
}
iota(h,h+N,0);
p[1] = -1;
dfs(1);
decomp(1);
for (int i =1 ; i<= n; i++){
//printf("%d pos %d\n",i,pos[i]);
}
for (int i = 1; i < n; i++){
if (d[A[i]] < d[B[i]]) swap(A[i],B[i]);
//printf("edge %d: %d -> %d\n",A[i],B[i]);
}
for (int i = 1; i < n; i++){
add(i,i+1);
}
ll ans = 0;
for (int i = 1; i < n; i++){
//printf("querying pos[%d] = %d\n",A[i],pos[A[i]]);
int num = query(pos[A[i]]);
//printf("edge connecting %d to %d has been used %d times\n",A[i],B[i],num);
ans += min((ll)num*C1[i],(ll)C2[i]);
}
printf("%lld",ans);
}
Compilation message
putovanje.cpp: In function 'void add(int, int)':
putovanje.cpp:63:9: warning: unused variable 'ans' [-Wunused-variable]
int ans = 0;
^~~
putovanje.cpp: In function 'int main()':
putovanje.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
putovanje.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&A[i],&B[i],&C1[i],&C2[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5888 KB |
Output is correct |
2 |
Correct |
9 ms |
6016 KB |
Output is correct |
3 |
Correct |
10 ms |
6016 KB |
Output is correct |
4 |
Correct |
9 ms |
6016 KB |
Output is correct |
5 |
Correct |
12 ms |
6016 KB |
Output is correct |
6 |
Correct |
8 ms |
5888 KB |
Output is correct |
7 |
Correct |
8 ms |
5888 KB |
Output is correct |
8 |
Correct |
12 ms |
6016 KB |
Output is correct |
9 |
Correct |
9 ms |
6016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
91 ms |
14328 KB |
Output is correct |
2 |
Correct |
93 ms |
15072 KB |
Output is correct |
3 |
Correct |
99 ms |
16120 KB |
Output is correct |
4 |
Correct |
114 ms |
15736 KB |
Output is correct |
5 |
Correct |
8 ms |
6016 KB |
Output is correct |
6 |
Correct |
93 ms |
14112 KB |
Output is correct |
7 |
Correct |
67 ms |
12000 KB |
Output is correct |
8 |
Correct |
95 ms |
14176 KB |
Output is correct |
9 |
Correct |
80 ms |
14436 KB |
Output is correct |
10 |
Correct |
80 ms |
14140 KB |
Output is correct |
11 |
Correct |
93 ms |
14916 KB |
Output is correct |
12 |
Correct |
93 ms |
14844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
5888 KB |
Output is correct |
2 |
Correct |
9 ms |
6016 KB |
Output is correct |
3 |
Correct |
10 ms |
6016 KB |
Output is correct |
4 |
Correct |
9 ms |
6016 KB |
Output is correct |
5 |
Correct |
12 ms |
6016 KB |
Output is correct |
6 |
Correct |
8 ms |
5888 KB |
Output is correct |
7 |
Correct |
8 ms |
5888 KB |
Output is correct |
8 |
Correct |
12 ms |
6016 KB |
Output is correct |
9 |
Correct |
9 ms |
6016 KB |
Output is correct |
10 |
Correct |
91 ms |
14328 KB |
Output is correct |
11 |
Correct |
93 ms |
15072 KB |
Output is correct |
12 |
Correct |
99 ms |
16120 KB |
Output is correct |
13 |
Correct |
114 ms |
15736 KB |
Output is correct |
14 |
Correct |
8 ms |
6016 KB |
Output is correct |
15 |
Correct |
93 ms |
14112 KB |
Output is correct |
16 |
Correct |
67 ms |
12000 KB |
Output is correct |
17 |
Correct |
95 ms |
14176 KB |
Output is correct |
18 |
Correct |
80 ms |
14436 KB |
Output is correct |
19 |
Correct |
80 ms |
14140 KB |
Output is correct |
20 |
Correct |
93 ms |
14916 KB |
Output is correct |
21 |
Correct |
93 ms |
14844 KB |
Output is correct |
22 |
Correct |
167 ms |
12408 KB |
Output is correct |
23 |
Correct |
144 ms |
11616 KB |
Output is correct |
24 |
Correct |
166 ms |
12356 KB |
Output is correct |
25 |
Correct |
9 ms |
6016 KB |
Output is correct |
26 |
Correct |
64 ms |
8936 KB |
Output is correct |
27 |
Correct |
135 ms |
11384 KB |
Output is correct |
28 |
Correct |
73 ms |
13536 KB |
Output is correct |
29 |
Correct |
83 ms |
14840 KB |
Output is correct |
30 |
Correct |
88 ms |
14840 KB |
Output is correct |
31 |
Correct |
10 ms |
6016 KB |
Output is correct |