# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
209994 | 2020-03-16T08:12:28 Z | SamAnd | Putovanje (COCI20_putovanje) | C++17 | 200 ms | 32760 KB |
#include <bits/stdc++.h> using namespace std; #define m_p make_pair const int N = 200005; int n; vector<int> a[N]; vector<pair<int, int> > b[N]; int tin[N], tout[N], ti; const int m = 19; int p[N][m]; void dfs0(int x, int p0) { tin[x] = ++ti; p[x][0] = p0; for (int i = 1; i < m; ++i) p[x][i] = p[p[x][i - 1]][i - 1]; for (int i = 0; i < a[x].size(); ++i) { int h = a[x][i]; if (h == p0) continue; dfs0(h, x); } tout[x] = ti; } bool isp(int x, int y) { return (tin[x] <= tin[y] && tin[y] <= tout[x]); } int lca(int x, int y) { if (isp(x, y)) return x; if (isp(y, x)) return y; for (int i = m - 1; i >= 0; --i) { if (!isp(p[x][i], y)) x = p[x][i]; } return p[x][0]; } long long ans; int q[N]; void dfs(int x, int p) { for (int i = 0; i < a[x].size(); ++i) { int h = a[x][i]; if (h == p) continue; dfs(h, x); q[x] += q[h]; } for (int i = 0; i < a[x].size(); ++i) { int h = a[x][i]; if (h == p) { ans += min(b[x][i].second * 1LL, b[x][i].first * 1LL * q[x]); } } } int main() { scanf("%d", &n); for (int i = 0; i < n - 1; ++i) { int x, y, c1, c2; scanf("%d%d%d%d", &x, &y, &c1, &c2); a[x].push_back(y); a[y].push_back(x); b[x].push_back(m_p(c1, c2)); b[y].push_back(m_p(c1, c2)); } dfs0(1, 1); for (int i = 1; i < n; ++i) { int u = lca(i, i + 1); q[u] -= 2; q[i]++; q[i + 1]++; } dfs(1, 1); printf("%lld\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9720 KB | Output is correct |
2 | Correct | 13 ms | 9976 KB | Output is correct |
3 | Correct | 12 ms | 9976 KB | Output is correct |
4 | Correct | 14 ms | 10104 KB | Output is correct |
5 | Correct | 13 ms | 10104 KB | Output is correct |
6 | Correct | 11 ms | 9720 KB | Output is correct |
7 | Correct | 11 ms | 9848 KB | Output is correct |
8 | Correct | 12 ms | 9976 KB | Output is correct |
9 | Correct | 13 ms | 10104 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 157 ms | 28920 KB | Output is correct |
2 | Correct | 154 ms | 30200 KB | Output is correct |
3 | Correct | 165 ms | 32760 KB | Output is correct |
4 | Correct | 200 ms | 32256 KB | Output is correct |
5 | Correct | 11 ms | 9848 KB | Output is correct |
6 | Correct | 147 ms | 28408 KB | Output is correct |
7 | Correct | 96 ms | 23544 KB | Output is correct |
8 | Correct | 177 ms | 28920 KB | Output is correct |
9 | Correct | 107 ms | 29688 KB | Output is correct |
10 | Correct | 105 ms | 29176 KB | Output is correct |
11 | Correct | 114 ms | 30840 KB | Output is correct |
12 | Correct | 130 ms | 30968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9720 KB | Output is correct |
2 | Correct | 13 ms | 9976 KB | Output is correct |
3 | Correct | 12 ms | 9976 KB | Output is correct |
4 | Correct | 14 ms | 10104 KB | Output is correct |
5 | Correct | 13 ms | 10104 KB | Output is correct |
6 | Correct | 11 ms | 9720 KB | Output is correct |
7 | Correct | 11 ms | 9848 KB | Output is correct |
8 | Correct | 12 ms | 9976 KB | Output is correct |
9 | Correct | 13 ms | 10104 KB | Output is correct |
10 | Correct | 157 ms | 28920 KB | Output is correct |
11 | Correct | 154 ms | 30200 KB | Output is correct |
12 | Correct | 165 ms | 32760 KB | Output is correct |
13 | Correct | 200 ms | 32256 KB | Output is correct |
14 | Correct | 11 ms | 9848 KB | Output is correct |
15 | Correct | 147 ms | 28408 KB | Output is correct |
16 | Correct | 96 ms | 23544 KB | Output is correct |
17 | Correct | 177 ms | 28920 KB | Output is correct |
18 | Correct | 107 ms | 29688 KB | Output is correct |
19 | Correct | 105 ms | 29176 KB | Output is correct |
20 | Correct | 114 ms | 30840 KB | Output is correct |
21 | Correct | 130 ms | 30968 KB | Output is correct |
22 | Correct | 189 ms | 26872 KB | Output is correct |
23 | Correct | 164 ms | 24824 KB | Output is correct |
24 | Correct | 195 ms | 26488 KB | Output is correct |
25 | Correct | 11 ms | 9848 KB | Output is correct |
26 | Correct | 73 ms | 17272 KB | Output is correct |
27 | Correct | 157 ms | 24184 KB | Output is correct |
28 | Correct | 97 ms | 27256 KB | Output is correct |
29 | Correct | 116 ms | 30968 KB | Output is correct |
30 | Correct | 115 ms | 30584 KB | Output is correct |
31 | Correct | 12 ms | 10104 KB | Output is correct |