# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
201043 | 2020-02-09T07:20:28 Z | gs14004 | Putovanje (COCI20_putovanje) | C++17 | 209 ms | 20264 KB |
#include <bits/stdc++.h> #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() using namespace std; using pi = pair<int, int>; using lint = long long; const int mod = 1e9 + 7; const int MAXN = 200005; struct edg{ int pos, c[2]; }; int n; vector<edg> gph[MAXN]; int par[18][MAXN], pae[MAXN][2], dep[MAXN], dx[MAXN]; void dfs2(int x, int p){ for(auto &i : gph[x]){ if(i.pos != p){ dfs2(i.pos, x); dx[x] += dx[i.pos]; } } } void dfs(int x, int p){ for(auto &i : gph[x]){ if(i.pos != p){ dep[i.pos] = dep[x] + 1; par[0][i.pos] = x; pae[i.pos][0] = i.c[0]; pae[i.pos][1] = i.c[1]; dfs(i.pos, x); } } } int main(){ scanf("%d",&n); for(int i=1; i<n; i++){ int u, v, x, y; scanf("%d %d %d %d",&u,&v,&x,&y); edg e; e.pos = v, e.c[0] = x; e.c[1] = y; gph[u].push_back(e); e.pos = u; gph[v].push_back(e); } dfs(1, 0); for(int i=1; i<18; i++){ for(int j=1; j<=n; j++){ par[i][j] = par[i-1][par[i-1][j]]; } } auto lca = [&](int x, int y){ if(dep[x] < dep[y]) swap(x, y); int dx = dep[x] - dep[y]; for(int i=0; i<18; i++){ if((dx >> i) & 1) x = par[i][x]; } for(int i=17; i>=0; i--){ if(par[i][x] != par[i][y]){ x = par[i][x]; y = par[i][y]; } } if(x != y) return par[0][x]; return x; }; for(int i=2; i<=n; i++){ int l = lca(i - 1, i); dx[i]++; dx[i-1]++; dx[l] -= 2; } dfs2(1, 0); lint ret = 0; for(int i=2; i<=n; i++){ ret += min(1ll * pae[i][1], 1ll * pae[i][0] * dx[i]); } cout << ret << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 5112 KB | Output is correct |
2 | Correct | 9 ms | 5368 KB | Output is correct |
3 | Correct | 9 ms | 5368 KB | Output is correct |
4 | Correct | 9 ms | 5368 KB | Output is correct |
5 | Correct | 9 ms | 5368 KB | Output is correct |
6 | Correct | 8 ms | 5112 KB | Output is correct |
7 | Correct | 8 ms | 5240 KB | Output is correct |
8 | Correct | 9 ms | 5240 KB | Output is correct |
9 | Correct | 9 ms | 5372 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 166 ms | 18040 KB | Output is correct |
2 | Correct | 142 ms | 19064 KB | Output is correct |
3 | Correct | 166 ms | 20264 KB | Output is correct |
4 | Correct | 194 ms | 20088 KB | Output is correct |
5 | Correct | 8 ms | 5240 KB | Output is correct |
6 | Correct | 149 ms | 17784 KB | Output is correct |
7 | Correct | 86 ms | 14328 KB | Output is correct |
8 | Correct | 158 ms | 17912 KB | Output is correct |
9 | Correct | 84 ms | 18552 KB | Output is correct |
10 | Correct | 86 ms | 18040 KB | Output is correct |
11 | Correct | 93 ms | 19192 KB | Output is correct |
12 | Correct | 87 ms | 19192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 5112 KB | Output is correct |
2 | Correct | 9 ms | 5368 KB | Output is correct |
3 | Correct | 9 ms | 5368 KB | Output is correct |
4 | Correct | 9 ms | 5368 KB | Output is correct |
5 | Correct | 9 ms | 5368 KB | Output is correct |
6 | Correct | 8 ms | 5112 KB | Output is correct |
7 | Correct | 8 ms | 5240 KB | Output is correct |
8 | Correct | 9 ms | 5240 KB | Output is correct |
9 | Correct | 9 ms | 5372 KB | Output is correct |
10 | Correct | 166 ms | 18040 KB | Output is correct |
11 | Correct | 142 ms | 19064 KB | Output is correct |
12 | Correct | 166 ms | 20264 KB | Output is correct |
13 | Correct | 194 ms | 20088 KB | Output is correct |
14 | Correct | 8 ms | 5240 KB | Output is correct |
15 | Correct | 149 ms | 17784 KB | Output is correct |
16 | Correct | 86 ms | 14328 KB | Output is correct |
17 | Correct | 158 ms | 17912 KB | Output is correct |
18 | Correct | 84 ms | 18552 KB | Output is correct |
19 | Correct | 86 ms | 18040 KB | Output is correct |
20 | Correct | 93 ms | 19192 KB | Output is correct |
21 | Correct | 87 ms | 19192 KB | Output is correct |
22 | Correct | 209 ms | 17528 KB | Output is correct |
23 | Correct | 166 ms | 16172 KB | Output is correct |
24 | Correct | 193 ms | 17376 KB | Output is correct |
25 | Correct | 9 ms | 5240 KB | Output is correct |
26 | Correct | 57 ms | 10872 KB | Output is correct |
27 | Correct | 153 ms | 15740 KB | Output is correct |
28 | Correct | 76 ms | 17016 KB | Output is correct |
29 | Correct | 88 ms | 19192 KB | Output is correct |
30 | Correct | 88 ms | 19192 KB | Output is correct |
31 | Correct | 10 ms | 5368 KB | Output is correct |