#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef pair<int, int> ii;
int N, depth[100000], st[100000], parent[100000], hchild[100000], head[100000], preo[100000], post[100000], cnt = 0;
vector<int> adjlist[100000];
int dfs1(int v) {
int ms = 0;
for (int i: adjlist[v]) {
if (i == parent[v]) continue;
depth[i] = depth[v] + 1;
parent[i] = v;
int temp = dfs1(i);
st[v] += temp;
if (temp > ms) ms = temp, hchild[v] = i;
}
return st[v];
}
void dfs2(int v) {
preo[cnt] = v;
post[v] = cnt++;
if (hchild[v] != -1) {
head[hchild[v]] = head[v];
dfs2(hchild[v]);
}
for (int i: adjlist[v]) {
if (i == parent[v]) continue;
if (i == hchild[v]) continue;
head[i] = i;
dfs2(i);
}
}
struct Fenwick {
int s;
vector<int> f;
Fenwick(int N) {
s = N;
f = vector<int>(s + 1);
}
void update(int i, int v) {
for (; i <= s; i += i & -i) f[i] += v;
}
int query(int a) {
int ans = 0;
for (; a > 0; a -= a & -a) ans += f[a];
return ans;
}
};
int main() {
int A, B, C, D;
scanf("%d", &N);
map<ii, ii> edges;
for (int i = 1; i < N; ++i) {
scanf("%d %d %d %d", &A, &B, &C, &D);
adjlist[A - 1].push_back(B - 1);
adjlist[B - 1].push_back(A - 1);
edges[ii(min(A - 1, B - 1), max(A - 1, B - 1))] = ii(C, D);
}
depth[0] = head[0] = 0, parent[0] = -1;
fill_n(st, N, 1);
fill_n(hchild, N, -1);
dfs1(0);
dfs2(0);
Fenwick f(N);
for (int i = 1; i < N; ++i) {
A = i - 1, B = i;
for (; head[A] != head[B]; B = parent[head[B]]) {
if (depth[head[B]] < depth[head[A]]) swap(A, B);
f.update(post[B] + 2, -1);
f.update(post[head[B]] + 1, 1);
}
if (depth[B] < depth[A]) swap(A, B);
f.update(post[A] + 2, 1);
f.update(post[B] + 2, -1);
}
long long ans = 0;
for (pair<ii, ii> i: edges) {
A = i.first.first, B = i.first.second, C = i.second.first, D = i.second.second;
if (depth[B] < depth[A]) swap(A, B);
ans += min((long long) C * (long long) f.query(post[B] + 1), (long long) D);
}
printf("%lld", ans);
return 0;
}
Compilation message
putovanje.cpp: In function 'int main()':
putovanje.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
putovanje.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &A, &B, &C, &D);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2688 KB |
Output is correct |
2 |
Correct |
8 ms |
2944 KB |
Output is correct |
3 |
Correct |
8 ms |
2944 KB |
Output is correct |
4 |
Correct |
8 ms |
2944 KB |
Output is correct |
5 |
Correct |
8 ms |
2944 KB |
Output is correct |
6 |
Correct |
6 ms |
2688 KB |
Output is correct |
7 |
Correct |
8 ms |
2816 KB |
Output is correct |
8 |
Correct |
8 ms |
2816 KB |
Output is correct |
9 |
Correct |
8 ms |
2944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
152 ms |
17144 KB |
Output is correct |
2 |
Correct |
158 ms |
18216 KB |
Output is correct |
3 |
Correct |
166 ms |
19960 KB |
Output is correct |
4 |
Correct |
171 ms |
19576 KB |
Output is correct |
5 |
Correct |
6 ms |
2816 KB |
Output is correct |
6 |
Correct |
137 ms |
16760 KB |
Output is correct |
7 |
Correct |
88 ms |
13176 KB |
Output is correct |
8 |
Correct |
157 ms |
17272 KB |
Output is correct |
9 |
Correct |
112 ms |
17656 KB |
Output is correct |
10 |
Correct |
109 ms |
17144 KB |
Output is correct |
11 |
Correct |
106 ms |
18296 KB |
Output is correct |
12 |
Correct |
111 ms |
18424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2688 KB |
Output is correct |
2 |
Correct |
8 ms |
2944 KB |
Output is correct |
3 |
Correct |
8 ms |
2944 KB |
Output is correct |
4 |
Correct |
8 ms |
2944 KB |
Output is correct |
5 |
Correct |
8 ms |
2944 KB |
Output is correct |
6 |
Correct |
6 ms |
2688 KB |
Output is correct |
7 |
Correct |
8 ms |
2816 KB |
Output is correct |
8 |
Correct |
8 ms |
2816 KB |
Output is correct |
9 |
Correct |
8 ms |
2944 KB |
Output is correct |
10 |
Correct |
152 ms |
17144 KB |
Output is correct |
11 |
Correct |
158 ms |
18216 KB |
Output is correct |
12 |
Correct |
166 ms |
19960 KB |
Output is correct |
13 |
Correct |
171 ms |
19576 KB |
Output is correct |
14 |
Correct |
6 ms |
2816 KB |
Output is correct |
15 |
Correct |
137 ms |
16760 KB |
Output is correct |
16 |
Correct |
88 ms |
13176 KB |
Output is correct |
17 |
Correct |
157 ms |
17272 KB |
Output is correct |
18 |
Correct |
112 ms |
17656 KB |
Output is correct |
19 |
Correct |
109 ms |
17144 KB |
Output is correct |
20 |
Correct |
106 ms |
18296 KB |
Output is correct |
21 |
Correct |
111 ms |
18424 KB |
Output is correct |
22 |
Correct |
245 ms |
14844 KB |
Output is correct |
23 |
Correct |
214 ms |
13432 KB |
Output is correct |
24 |
Correct |
249 ms |
14840 KB |
Output is correct |
25 |
Correct |
7 ms |
2816 KB |
Output is correct |
26 |
Correct |
85 ms |
8312 KB |
Output is correct |
27 |
Correct |
207 ms |
12920 KB |
Output is correct |
28 |
Correct |
89 ms |
15992 KB |
Output is correct |
29 |
Correct |
106 ms |
18424 KB |
Output is correct |
30 |
Correct |
110 ms |
18300 KB |
Output is correct |
31 |
Correct |
7 ms |
2944 KB |
Output is correct |