#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]
scanf("%d",&n);
~~~~~^~~~~~~~~
putovanje.cpp:74:10: 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[i],&d[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5116 KB |
Output is correct |
2 |
Correct |
9 ms |
5368 KB |
Output is correct |
3 |
Correct |
9 ms |
5368 KB |
Output is correct |
4 |
Correct |
10 ms |
5496 KB |
Output is correct |
5 |
Correct |
9 ms |
5496 KB |
Output is correct |
6 |
Correct |
8 ms |
5240 KB |
Output is correct |
7 |
Correct |
8 ms |
5240 KB |
Output is correct |
8 |
Correct |
9 ms |
5368 KB |
Output is correct |
9 |
Correct |
10 ms |
5368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
136 ms |
20856 KB |
Output is correct |
2 |
Correct |
143 ms |
22140 KB |
Output is correct |
3 |
Correct |
148 ms |
23928 KB |
Output is correct |
4 |
Correct |
170 ms |
23544 KB |
Output is correct |
5 |
Correct |
8 ms |
5240 KB |
Output is correct |
6 |
Correct |
129 ms |
20472 KB |
Output is correct |
7 |
Correct |
79 ms |
16632 KB |
Output is correct |
8 |
Correct |
147 ms |
20728 KB |
Output is correct |
9 |
Correct |
85 ms |
21112 KB |
Output is correct |
10 |
Correct |
79 ms |
20600 KB |
Output is correct |
11 |
Correct |
85 ms |
21880 KB |
Output is correct |
12 |
Correct |
86 ms |
21880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5116 KB |
Output is correct |
2 |
Correct |
9 ms |
5368 KB |
Output is correct |
3 |
Correct |
9 ms |
5368 KB |
Output is correct |
4 |
Correct |
10 ms |
5496 KB |
Output is correct |
5 |
Correct |
9 ms |
5496 KB |
Output is correct |
6 |
Correct |
8 ms |
5240 KB |
Output is correct |
7 |
Correct |
8 ms |
5240 KB |
Output is correct |
8 |
Correct |
9 ms |
5368 KB |
Output is correct |
9 |
Correct |
10 ms |
5368 KB |
Output is correct |
10 |
Correct |
136 ms |
20856 KB |
Output is correct |
11 |
Correct |
143 ms |
22140 KB |
Output is correct |
12 |
Correct |
148 ms |
23928 KB |
Output is correct |
13 |
Correct |
170 ms |
23544 KB |
Output is correct |
14 |
Correct |
8 ms |
5240 KB |
Output is correct |
15 |
Correct |
129 ms |
20472 KB |
Output is correct |
16 |
Correct |
79 ms |
16632 KB |
Output is correct |
17 |
Correct |
147 ms |
20728 KB |
Output is correct |
18 |
Correct |
85 ms |
21112 KB |
Output is correct |
19 |
Correct |
79 ms |
20600 KB |
Output is correct |
20 |
Correct |
85 ms |
21880 KB |
Output is correct |
21 |
Correct |
86 ms |
21880 KB |
Output is correct |
22 |
Correct |
133 ms |
18184 KB |
Output is correct |
23 |
Correct |
110 ms |
16632 KB |
Output is correct |
24 |
Correct |
132 ms |
18168 KB |
Output is correct |
25 |
Correct |
8 ms |
5240 KB |
Output is correct |
26 |
Correct |
49 ms |
11128 KB |
Output is correct |
27 |
Correct |
101 ms |
16120 KB |
Output is correct |
28 |
Correct |
74 ms |
19436 KB |
Output is correct |
29 |
Correct |
85 ms |
21880 KB |
Output is correct |
30 |
Correct |
87 ms |
21880 KB |
Output is correct |
31 |
Correct |
9 ms |
5368 KB |
Output is correct |