#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;
int n;
struct UnionFind {
vector <int> v[MAXN];
int connected[MAXN];
int par[MAXN];
void init() {
REP(i, MAXN) {
v[i].clear();
par[i] = i;
connected[i] = 0;
v[i].pb(i);
}
}
void merge(int a, int b) {
a = par[a];
b = par[b];
if ((int)v[a].size() < (int)v[b].size()) swap(a, b);
for (auto x : v[b]) {
if (par[x - 1] == a) connected[a]++;
if (par[x + 1] == a) connected[a]++;
v[a].pb(x);
}
for (auto x : v[b]) par[x] = a;
connected[a] += connected[b];
}
int get(int x) {
x = par[x];
int ret = ((int)v[x].size() - connected[x]) * 2;
if (par[1] == x) ret--;
if (par[n] == x) ret--;
return ret;
}
};
UnionFind Uf;
int c[MAXN], d[MAXN];
int cnt[MAXN];
vector <pii> v[MAXN];
void dfs(int cvor, int par, int in) {
for (auto ncvor : v[cvor]) {
if (ncvor.fi == par) continue;
dfs(ncvor.fi, cvor, ncvor.sec);
Uf.merge(cvor, ncvor.fi);
}
if (in != -1) cnt[in] = Uf.get(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});
}
Uf.init();
dfs(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:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
putovanje.cpp:82: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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
17528 KB |
Output is correct |
2 |
Correct |
26 ms |
17656 KB |
Output is correct |
3 |
Correct |
24 ms |
17656 KB |
Output is correct |
4 |
Correct |
25 ms |
17656 KB |
Output is correct |
5 |
Correct |
24 ms |
17712 KB |
Output is correct |
6 |
Correct |
22 ms |
17528 KB |
Output is correct |
7 |
Correct |
24 ms |
17528 KB |
Output is correct |
8 |
Correct |
24 ms |
17656 KB |
Output is correct |
9 |
Correct |
26 ms |
17656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
112 ms |
30068 KB |
Output is correct |
2 |
Correct |
120 ms |
31860 KB |
Output is correct |
3 |
Correct |
128 ms |
33908 KB |
Output is correct |
4 |
Correct |
139 ms |
32372 KB |
Output is correct |
5 |
Correct |
24 ms |
17656 KB |
Output is correct |
6 |
Correct |
119 ms |
29688 KB |
Output is correct |
7 |
Correct |
85 ms |
27128 KB |
Output is correct |
8 |
Correct |
116 ms |
29684 KB |
Output is correct |
9 |
Correct |
91 ms |
29304 KB |
Output is correct |
10 |
Correct |
88 ms |
28916 KB |
Output is correct |
11 |
Correct |
90 ms |
29812 KB |
Output is correct |
12 |
Correct |
95 ms |
29708 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
17528 KB |
Output is correct |
2 |
Correct |
26 ms |
17656 KB |
Output is correct |
3 |
Correct |
24 ms |
17656 KB |
Output is correct |
4 |
Correct |
25 ms |
17656 KB |
Output is correct |
5 |
Correct |
24 ms |
17712 KB |
Output is correct |
6 |
Correct |
22 ms |
17528 KB |
Output is correct |
7 |
Correct |
24 ms |
17528 KB |
Output is correct |
8 |
Correct |
24 ms |
17656 KB |
Output is correct |
9 |
Correct |
26 ms |
17656 KB |
Output is correct |
10 |
Correct |
112 ms |
30068 KB |
Output is correct |
11 |
Correct |
120 ms |
31860 KB |
Output is correct |
12 |
Correct |
128 ms |
33908 KB |
Output is correct |
13 |
Correct |
139 ms |
32372 KB |
Output is correct |
14 |
Correct |
24 ms |
17656 KB |
Output is correct |
15 |
Correct |
119 ms |
29688 KB |
Output is correct |
16 |
Correct |
85 ms |
27128 KB |
Output is correct |
17 |
Correct |
116 ms |
29684 KB |
Output is correct |
18 |
Correct |
91 ms |
29304 KB |
Output is correct |
19 |
Correct |
88 ms |
28916 KB |
Output is correct |
20 |
Correct |
90 ms |
29812 KB |
Output is correct |
21 |
Correct |
95 ms |
29708 KB |
Output is correct |
22 |
Correct |
162 ms |
24464 KB |
Output is correct |
23 |
Correct |
134 ms |
23800 KB |
Output is correct |
24 |
Correct |
147 ms |
24432 KB |
Output is correct |
25 |
Correct |
27 ms |
17656 KB |
Output is correct |
26 |
Correct |
72 ms |
20724 KB |
Output is correct |
27 |
Correct |
124 ms |
23408 KB |
Output is correct |
28 |
Correct |
79 ms |
28020 KB |
Output is correct |
29 |
Correct |
98 ms |
29812 KB |
Output is correct |
30 |
Correct |
99 ms |
29812 KB |
Output is correct |
31 |
Correct |
25 ms |
17784 KB |
Output is correct |