# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
984213 | 2024-05-16T11:37:25 Z | Alkaser_ID | Road Closures (APIO21_roads) | C++17 | 62 ms | 15520 KB |
#include "roads.h" using namespace std; #include <bits/stdc++.h> typedef long long ll; vector<ll> adj[200005]; std::vector<long long> minimum_closure_costs(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W) { ll n = N; bool sb1 = true, sb2 = true; for(int i=0;i<n-1;i++) { if(U[i] != 0) sb1 = false; if(U[i] != i || V[i] != i+1) sb2 = false; ll u = U[i],v = V[i]; adj[u].push_back(v); adj[v].push_back(u); } if(sb1){ vector<ll> f; for(ll i=0;i<n-1;++i) f.push_back(W[i]); sort(f.begin(),f.end()); ll res = 0; vector<ll> ans; ans.push_back(res); for(ll i=0;i<n-1;++i){ res += f[i]; ans.push_back(res); } reverse(ans.begin(),ans.end()); return ans; } if(sb2){ ll sm =0; for(ll i=0;i<n-1;++i) sm += W[i]; vector<ll> ans; ans.push_back(sm); vector<ll> dp0(n+3,0),dp1(n+3,0); dp0[0] = 0; dp1[0] = W[0]; for(ll i=1;i<n-1;++i){ dp0[i] = dp1[i-1]; dp1[i] = min(dp0[i-1],dp1[i-1]) + W[i]; } ans.push_back(min(dp0[n-2],dp1[n-2])); for(ll i=2;i<n;++i) ans.push_back(0); return ans; } } /* 5 0 1 1 0 2 4 0 3 3 2 4 2 4 0 1 5 2 0 10 0 3 5 6 0 1 2 1 2 4 2 3 4 3 4 3 4 5 6 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 4952 KB | Output is correct |
2 | Correct | 2 ms | 5212 KB | Output is correct |
3 | Correct | 2 ms | 5212 KB | Output is correct |
4 | Correct | 3 ms | 5212 KB | Output is correct |
5 | Correct | 1 ms | 4956 KB | Output is correct |
6 | Correct | 1 ms | 4956 KB | Output is correct |
7 | Correct | 2 ms | 4960 KB | Output is correct |
8 | Correct | 3 ms | 5212 KB | Output is correct |
9 | Correct | 3 ms | 5208 KB | Output is correct |
10 | Correct | 2 ms | 4956 KB | Output is correct |
11 | Correct | 1 ms | 4956 KB | Output is correct |
12 | Correct | 24 ms | 10104 KB | Output is correct |
13 | Correct | 40 ms | 13652 KB | Output is correct |
14 | Correct | 45 ms | 12832 KB | Output is correct |
15 | Correct | 62 ms | 13600 KB | Output is correct |
16 | Correct | 47 ms | 13640 KB | Output is correct |
17 | Correct | 52 ms | 13644 KB | Output is correct |
18 | Correct | 1 ms | 4956 KB | Output is correct |
19 | Correct | 42 ms | 12944 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4956 KB | Output is correct |
2 | Correct | 39 ms | 12036 KB | Output is correct |
3 | Correct | 44 ms | 14740 KB | Output is correct |
4 | Correct | 45 ms | 15356 KB | Output is correct |
5 | Correct | 44 ms | 15520 KB | Output is correct |
6 | Correct | 3 ms | 5184 KB | Output is correct |
7 | Correct | 2 ms | 5196 KB | Output is correct |
8 | Correct | 3 ms | 5212 KB | Output is correct |
9 | Correct | 1 ms | 4956 KB | Output is correct |
10 | Correct | 1 ms | 4956 KB | Output is correct |
11 | Correct | 2 ms | 4956 KB | Output is correct |
12 | Correct | 24 ms | 10696 KB | Output is correct |
13 | Correct | 43 ms | 14672 KB | Output is correct |
14 | Correct | 2 ms | 4956 KB | Output is correct |
15 | Correct | 36 ms | 13708 KB | Output is correct |
16 | Correct | 40 ms | 14448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4956 KB | Output is correct |
2 | Incorrect | 1 ms | 4956 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4956 KB | Output is correct |
2 | Incorrect | 1 ms | 4956 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 48 ms | 13584 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 48 ms | 13584 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 4952 KB | Output is correct |
2 | Correct | 2 ms | 5212 KB | Output is correct |
3 | Correct | 2 ms | 5212 KB | Output is correct |
4 | Correct | 3 ms | 5212 KB | Output is correct |
5 | Correct | 1 ms | 4956 KB | Output is correct |
6 | Correct | 1 ms | 4956 KB | Output is correct |
7 | Correct | 2 ms | 4960 KB | Output is correct |
8 | Correct | 3 ms | 5212 KB | Output is correct |
9 | Correct | 3 ms | 5208 KB | Output is correct |
10 | Correct | 2 ms | 4956 KB | Output is correct |
11 | Correct | 1 ms | 4956 KB | Output is correct |
12 | Correct | 24 ms | 10104 KB | Output is correct |
13 | Correct | 40 ms | 13652 KB | Output is correct |
14 | Correct | 45 ms | 12832 KB | Output is correct |
15 | Correct | 62 ms | 13600 KB | Output is correct |
16 | Correct | 47 ms | 13640 KB | Output is correct |
17 | Correct | 52 ms | 13644 KB | Output is correct |
18 | Correct | 1 ms | 4956 KB | Output is correct |
19 | Correct | 42 ms | 12944 KB | Output is correct |
20 | Correct | 1 ms | 4956 KB | Output is correct |
21 | Correct | 39 ms | 12036 KB | Output is correct |
22 | Correct | 44 ms | 14740 KB | Output is correct |
23 | Correct | 45 ms | 15356 KB | Output is correct |
24 | Correct | 44 ms | 15520 KB | Output is correct |
25 | Correct | 3 ms | 5184 KB | Output is correct |
26 | Correct | 2 ms | 5196 KB | Output is correct |
27 | Correct | 3 ms | 5212 KB | Output is correct |
28 | Correct | 1 ms | 4956 KB | Output is correct |
29 | Correct | 1 ms | 4956 KB | Output is correct |
30 | Correct | 2 ms | 4956 KB | Output is correct |
31 | Correct | 24 ms | 10696 KB | Output is correct |
32 | Correct | 43 ms | 14672 KB | Output is correct |
33 | Correct | 2 ms | 4956 KB | Output is correct |
34 | Correct | 36 ms | 13708 KB | Output is correct |
35 | Correct | 40 ms | 14448 KB | Output is correct |
36 | Correct | 1 ms | 4956 KB | Output is correct |
37 | Incorrect | 1 ms | 4956 KB | Output isn't correct |
38 | Halted | 0 ms | 0 KB | - |