/******************************
* author : @marvinthang *
* date : 14 / 11 / 2021 *
******************************/
#include <bits/stdc++.h>
using namespace std;
#define superspeed ios_base::sync_with_stdio(false);\
cin.tie(NULL);\
//cout.tie(NULL);
#define file(name) freopen(name".inp", "r", stdin);\
freopen(name".out", "w", stdout);
const int MOD = 1e9 + 7; // 998244353;
const double PI = 3.1415926535897932384626433832795; // acos((db)-1); atan(-1.0);
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const long long oo = 1e18;
const int MAX = 2e5 + 5;
const int LOG = 18;
struct EDGE {
int u, v, cost1, costfull;
bool operator < (const EDGE &a) const {
return u == a.u ? v < a.v : u < a.u;
}
};
int numNode;
EDGE edges[MAX];
vector <int> adj[MAX];
int par[MAX], pref[MAX], anc[MAX][LOG], depth[MAX];
int findEdge(int u, int v) {
if (u > v) swap(u, v);
EDGE tmp = {u, v, 0, 0};
int l = 1, r = numNode - 1, res = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (edges[mid].u == u && edges[mid].v == v) return mid;
if (edges[mid] < tmp) l = mid + 1;
else r = mid - 1;
}
return res;
}
void dfs(int u) {
depth[u] = depth[anc[u][0]] + 1;
for (int i = 1; i < LOG; ++i) anc[u][i] = anc[anc[u][i - 1]][i - 1];
for (auto &v: adj[u]) {
if (v == anc[u][0]) continue;
int id = findEdge(u, v);
par[v] = id;
anc[v][0] = u;
dfs(v);
}
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int i = LOG - 1; i >= 0; --i) {
if (depth[anc[u][i]] >= depth[v]) u = anc[u][i];
}
if (u == v) return u;
for (int i = LOG - 1; i >= 0; --i) {
if (anc[u][i] != anc[v][i]) {
u = anc[u][i];
v = anc[v][i];
}
}
return anc[u][0];
}
void dfs2(int u) {
for (auto &v: adj[u]) {
if (v == anc[u][0]) continue;
dfs2(v);
pref[par[u]] += pref[par[v]];
}
}
int main() {
superspeed;
cin >> numNode;
for (int i = 1; i < numNode; ++i) {
int u, v, c1, cfull;
cin >> u >> v >> c1 >> cfull;
adj[u].push_back(v);
adj[v].push_back(u);
if (u > v) swap(u, v);
edges[i] = {u, v, c1, cfull};
}
sort(edges + 1, edges + numNode);
dfs(1);
for (int i = 2; i <= numNode; ++i) {
int u = i - 1, v = i;
++pref[par[u]];
++pref[par[v]];
pref[par[lca(u, v)]] -= 2;
}
dfs2(1);
long long res = 0;
for (int i = 1; i < numNode; ++i) {
long long a = 1LL * edges[i].cost1 * pref[i];
long long b = edges[i].costfull;
res += min(a, b);
}
cout << res << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
5204 KB |
Output is correct |
3 |
Correct |
4 ms |
5300 KB |
Output is correct |
4 |
Correct |
5 ms |
5348 KB |
Output is correct |
5 |
Correct |
4 ms |
5332 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
5076 KB |
Output is correct |
8 |
Correct |
4 ms |
5204 KB |
Output is correct |
9 |
Correct |
4 ms |
5216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
155 ms |
21500 KB |
Output is correct |
2 |
Correct |
142 ms |
22744 KB |
Output is correct |
3 |
Correct |
202 ms |
24928 KB |
Output is correct |
4 |
Correct |
183 ms |
24596 KB |
Output is correct |
5 |
Correct |
3 ms |
5076 KB |
Output is correct |
6 |
Correct |
136 ms |
21152 KB |
Output is correct |
7 |
Correct |
88 ms |
16832 KB |
Output is correct |
8 |
Correct |
149 ms |
21580 KB |
Output is correct |
9 |
Correct |
85 ms |
22368 KB |
Output is correct |
10 |
Correct |
85 ms |
22096 KB |
Output is correct |
11 |
Correct |
90 ms |
23392 KB |
Output is correct |
12 |
Correct |
97 ms |
23544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
5204 KB |
Output is correct |
3 |
Correct |
4 ms |
5300 KB |
Output is correct |
4 |
Correct |
5 ms |
5348 KB |
Output is correct |
5 |
Correct |
4 ms |
5332 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
5076 KB |
Output is correct |
8 |
Correct |
4 ms |
5204 KB |
Output is correct |
9 |
Correct |
4 ms |
5216 KB |
Output is correct |
10 |
Correct |
155 ms |
21500 KB |
Output is correct |
11 |
Correct |
142 ms |
22744 KB |
Output is correct |
12 |
Correct |
202 ms |
24928 KB |
Output is correct |
13 |
Correct |
183 ms |
24596 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
136 ms |
21152 KB |
Output is correct |
16 |
Correct |
88 ms |
16832 KB |
Output is correct |
17 |
Correct |
149 ms |
21580 KB |
Output is correct |
18 |
Correct |
85 ms |
22368 KB |
Output is correct |
19 |
Correct |
85 ms |
22096 KB |
Output is correct |
20 |
Correct |
90 ms |
23392 KB |
Output is correct |
21 |
Correct |
97 ms |
23544 KB |
Output is correct |
22 |
Correct |
127 ms |
19628 KB |
Output is correct |
23 |
Correct |
121 ms |
17836 KB |
Output is correct |
24 |
Correct |
121 ms |
19344 KB |
Output is correct |
25 |
Correct |
4 ms |
5172 KB |
Output is correct |
26 |
Correct |
49 ms |
11404 KB |
Output is correct |
27 |
Correct |
102 ms |
17356 KB |
Output is correct |
28 |
Correct |
76 ms |
20248 KB |
Output is correct |
29 |
Correct |
97 ms |
23492 KB |
Output is correct |
30 |
Correct |
87 ms |
23148 KB |
Output is correct |
31 |
Correct |
4 ms |
5172 KB |
Output is correct |