# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
637628 | 2022-09-02T13:25:25 Z | 4EVER | Putovanje (COCI20_putovanje) | C++11 | 136 ms | 23464 KB |
#include <bits/stdc++.h> using namespace std; int n; vector<pair<int, int>> adj[200001]; int val[200001], cnt[200001], depth[200001], c[200001], d[200001]; int spt[19][200001]; void DFS(int u = 1, int par = -1){ for(auto x : adj[u]){ int v = x.first; if(v == par) continue; depth[v] = depth[u] + 1; spt[0][v] = u; for(int i = 1; i <= 18; i++) spt[i][v] = spt[i - 1][spt[i - 1][v]]; DFS(v, u); } } int LCA(int u, int v){ if(depth[u] < depth[v]) swap(u, v); int k = depth[u] - depth[v]; for(int i = 18; i >= 0; i--) if((k >> i) & 1) u = spt[i][u]; if(u == v) return u; for(int i = 18; i >= 0; i--) if(spt[i][u] != spt[i][v]){ u = spt[i][u]; v = spt[i][v]; } return spt[0][u]; } void reDFS(int u = 1, int par = -1, int id = -1){ for(auto x : adj[u]){ int v = x.first; int w = x.second; if(v == par) continue; reDFS(v, u, w); val[u] += val[v]; } if(id != -1) cnt[id] = val[u]; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define TASK "PUTOVANJE" if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } cin >> n; for(int i = 1; i < n; i++){ int u, v; cin >> u >> v; cin >> c[i] >> d[i]; adj[u].push_back({v, i}); adj[v].push_back({u, i}); } DFS(); for(int i = 2; i <= n; i++){ val[i]++; val[i - 1]++; val[LCA(i, i - 1)] -= 2; } reDFS(); long long res = 0; for(int i = 1; i < n; i++){ res += min((long long) c[i] * cnt[i], (long long) d[i]); } cout << res; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 5076 KB | Output is correct |
2 | Correct | 4 ms | 5332 KB | Output is correct |
3 | Correct | 4 ms | 5332 KB | Output is correct |
4 | Correct | 5 ms | 5332 KB | Output is correct |
5 | Correct | 4 ms | 5388 KB | Output is correct |
6 | Correct | 3 ms | 5076 KB | Output is correct |
7 | Correct | 3 ms | 5204 KB | Output is correct |
8 | Correct | 3 ms | 5204 KB | Output is correct |
9 | Correct | 3 ms | 5332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 119 ms | 20456 KB | Output is correct |
2 | Correct | 136 ms | 21708 KB | Output is correct |
3 | Correct | 115 ms | 23464 KB | Output is correct |
4 | Correct | 128 ms | 23164 KB | Output is correct |
5 | Correct | 3 ms | 5204 KB | Output is correct |
6 | Correct | 99 ms | 20080 KB | Output is correct |
7 | Correct | 60 ms | 16328 KB | Output is correct |
8 | Correct | 113 ms | 20332 KB | Output is correct |
9 | Correct | 53 ms | 20696 KB | Output is correct |
10 | Correct | 57 ms | 20328 KB | Output is correct |
11 | Correct | 57 ms | 21548 KB | Output is correct |
12 | Correct | 61 ms | 21512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 5076 KB | Output is correct |
2 | Correct | 4 ms | 5332 KB | Output is correct |
3 | Correct | 4 ms | 5332 KB | Output is correct |
4 | Correct | 5 ms | 5332 KB | Output is correct |
5 | Correct | 4 ms | 5388 KB | Output is correct |
6 | Correct | 3 ms | 5076 KB | Output is correct |
7 | Correct | 3 ms | 5204 KB | Output is correct |
8 | Correct | 3 ms | 5204 KB | Output is correct |
9 | Correct | 3 ms | 5332 KB | Output is correct |
10 | Correct | 119 ms | 20456 KB | Output is correct |
11 | Correct | 136 ms | 21708 KB | Output is correct |
12 | Correct | 115 ms | 23464 KB | Output is correct |
13 | Correct | 128 ms | 23164 KB | Output is correct |
14 | Correct | 3 ms | 5204 KB | Output is correct |
15 | Correct | 99 ms | 20080 KB | Output is correct |
16 | Correct | 60 ms | 16328 KB | Output is correct |
17 | Correct | 113 ms | 20332 KB | Output is correct |
18 | Correct | 53 ms | 20696 KB | Output is correct |
19 | Correct | 57 ms | 20328 KB | Output is correct |
20 | Correct | 57 ms | 21548 KB | Output is correct |
21 | Correct | 61 ms | 21512 KB | Output is correct |
22 | Correct | 95 ms | 17628 KB | Output is correct |
23 | Correct | 88 ms | 16260 KB | Output is correct |
24 | Correct | 96 ms | 17516 KB | Output is correct |
25 | Correct | 3 ms | 5204 KB | Output is correct |
26 | Correct | 38 ms | 10948 KB | Output is correct |
27 | Correct | 88 ms | 15692 KB | Output is correct |
28 | Correct | 48 ms | 19056 KB | Output is correct |
29 | Correct | 61 ms | 21536 KB | Output is correct |
30 | Correct | 60 ms | 21456 KB | Output is correct |
31 | Correct | 3 ms | 5332 KB | Output is correct |