#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;
#define TRACE(x) cerr << #x << " " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<
#define fi first
#define sec second
#define mp make_pair
#define pb push_back
const int MAXN = 200100;
const int LOG = 19;
int n, lca[LOG][MAXN];
int dub[MAXN];
int c[MAXN], d[MAXN];
int cnt[MAXN], p[MAXN], dp[MAXN];
vector <pii> v[MAXN];
void dfs(int cvor, int par, int d) {
dub[cvor] = d;
for (auto ncvor : v[cvor]) {
if (ncvor.fi == par) continue;
dfs(ncvor.fi, cvor, d + 1);
lca[0][ncvor.fi] = cvor;
}
}
int get_lca(int a, int b) {
if (dub[a] < dub[b]) swap(a, b);
for (int i = LOG - 1; i >= 0; i--) {
if (dub[a] - (1 << i) >= dub[b]) {
a = lca[i][a];
}
}
if (a == b) return a;
for (int i = LOG - 1; i >= 0; i--) {
if (lca[i][a] != lca[i][b]) {
a = lca[i][a];
b = lca[i][b];
}
}
return lca[0][a];
}
void rek(int cvor, int par, int in) {
for (auto ncvor : v[cvor]) {
if (ncvor.fi == par) continue;
rek(ncvor.fi, cvor, ncvor.sec);
dp[cvor] += dp[ncvor.fi];
}
dp[cvor] += p[cvor];
if (in != -1) cnt[in] = dp[cvor];
}
int main() {
scanf("%d",&n);
REP(i, n - 1) {
int a, b;
scanf("%d %d %d %d",&a,&b,&c[i],&d[i]);
v[a].pb({b, i});
v[b].pb({a, i});
}
dfs(1, -1, 0);
FOR(i, 1, LOG) {
FOR(j, 1, n + 1) {
lca[i][j] = lca[i - 1][lca[i - 1][j]];
}
}
FOR(i, 1, n) {
int l = get_lca(i, i + 1);
p[i]++;
p[i + 1]++;
p[l] -= 2;
}
rek(1, -1, -1);
ll sol = 0;
REP(i, n - 1) {
sol += min((ll)c[i] * cnt[i], (ll)d[i]);
}
printf("%lld\n",sol);
return 0;
}
Compilation message
putovanje.cpp: In function 'int main()':
putovanje.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
putovanje.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d %d %d %d",&a,&b,&c[i],&d[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
23128 KB |
Output is correct |
2 |
Correct |
4 ms |
23132 KB |
Output is correct |
3 |
Correct |
4 ms |
23128 KB |
Output is correct |
4 |
Correct |
4 ms |
23132 KB |
Output is correct |
5 |
Correct |
4 ms |
23156 KB |
Output is correct |
6 |
Correct |
3 ms |
23132 KB |
Output is correct |
7 |
Correct |
4 ms |
23196 KB |
Output is correct |
8 |
Correct |
5 ms |
23132 KB |
Output is correct |
9 |
Correct |
4 ms |
23132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
30804 KB |
Output is correct |
2 |
Correct |
66 ms |
32040 KB |
Output is correct |
3 |
Correct |
80 ms |
33392 KB |
Output is correct |
4 |
Correct |
77 ms |
32272 KB |
Output is correct |
5 |
Correct |
4 ms |
23128 KB |
Output is correct |
6 |
Correct |
65 ms |
30708 KB |
Output is correct |
7 |
Correct |
43 ms |
29008 KB |
Output is correct |
8 |
Correct |
69 ms |
30484 KB |
Output is correct |
9 |
Correct |
48 ms |
30468 KB |
Output is correct |
10 |
Correct |
47 ms |
30272 KB |
Output is correct |
11 |
Correct |
52 ms |
30768 KB |
Output is correct |
12 |
Correct |
51 ms |
30956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
23128 KB |
Output is correct |
2 |
Correct |
4 ms |
23132 KB |
Output is correct |
3 |
Correct |
4 ms |
23128 KB |
Output is correct |
4 |
Correct |
4 ms |
23132 KB |
Output is correct |
5 |
Correct |
4 ms |
23156 KB |
Output is correct |
6 |
Correct |
3 ms |
23132 KB |
Output is correct |
7 |
Correct |
4 ms |
23196 KB |
Output is correct |
8 |
Correct |
5 ms |
23132 KB |
Output is correct |
9 |
Correct |
4 ms |
23132 KB |
Output is correct |
10 |
Correct |
65 ms |
30804 KB |
Output is correct |
11 |
Correct |
66 ms |
32040 KB |
Output is correct |
12 |
Correct |
80 ms |
33392 KB |
Output is correct |
13 |
Correct |
77 ms |
32272 KB |
Output is correct |
14 |
Correct |
4 ms |
23128 KB |
Output is correct |
15 |
Correct |
65 ms |
30708 KB |
Output is correct |
16 |
Correct |
43 ms |
29008 KB |
Output is correct |
17 |
Correct |
69 ms |
30484 KB |
Output is correct |
18 |
Correct |
48 ms |
30468 KB |
Output is correct |
19 |
Correct |
47 ms |
30272 KB |
Output is correct |
20 |
Correct |
52 ms |
30768 KB |
Output is correct |
21 |
Correct |
51 ms |
30956 KB |
Output is correct |
22 |
Correct |
57 ms |
27476 KB |
Output is correct |
23 |
Correct |
50 ms |
26972 KB |
Output is correct |
24 |
Correct |
54 ms |
27224 KB |
Output is correct |
25 |
Correct |
4 ms |
23132 KB |
Output is correct |
26 |
Correct |
26 ms |
24924 KB |
Output is correct |
27 |
Correct |
48 ms |
26784 KB |
Output is correct |
28 |
Correct |
41 ms |
29760 KB |
Output is correct |
29 |
Correct |
51 ms |
30808 KB |
Output is correct |
30 |
Correct |
58 ms |
30772 KB |
Output is correct |
31 |
Correct |
4 ms |
23132 KB |
Output is correct |