#include<bits/stdc++.h>
#include "roads.h"
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 2e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
ll f[2002][2002];
ll tmp[maxN];
int k;
ll dp[maxN][2];
vector<pair<int, int>> adj[maxN];
void dfs(int u, int par)
{
for(auto a : adj[u])
{
int v = a.fi, w = a.se;
if(v == par) continue;
dfs(v, u);
for(int i=0; i<=k; i++) tmp[i] = f[u][i];
tmp[k] += f[v][0] + w;
for(int i=k-1; i>=0; i--)
tmp[i] = min(f[u][i] + f[v][0] + w, f[u][i + 1] + f[v][1]);
for(int i=k-1; i>=1; i--)
tmp[i] = min(tmp[i], tmp[i + 1]);
for(int i=0; i<=k; i++) f[u][i] = tmp[i];
if(u == 1 && v == 3)
{
// cout << f[1][1];exit(0);
}
}
}
vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W)
{
vector<ll> res;
bool ok = true;
ll sum = 0;
for(int i=0; i<n-1; i++)
{
int u = U[i] + 1, v = V[i] + 1, w = W[i];
//cout << u << " " << v << '\n';
sum += w;
if(U[i] != i || V[i] != i + 1) ok = false;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
if(adj[1].size() == n - 1)
{
vector<int> vc;
for(int i=0; i<n-1; i++) vc.pb(W[i]);
sort(vc.begin(), vc.end());
for(int i=0; i<n; i++)
{
res.pb(sum);
sum -= vc.back();
vc.pop_back();
}
return res;
}
if(ok)
{
res.pb(sum);
dp[1][1] = W[0];
for(int i=2; i<n; i++)
{
dp[i][0] = dp[i - 1][1];
dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + W[i - 1];
}
res.pb(min(dp[n - 1][0], dp[n - 1][1]));
while(res.size() != n) res.pb(0);
return res;
}
for(int _k=n-1; _k>=1; _k--)
{
k = _k;
memset(f, 0, sizeof f);
dfs(1, 0);
// cout << f[1][0];exit(0);
res.pb(f[1][0]);
}
res.pb(sum);
reverse(res.begin(), res.end());
return res;
}
/*void Solve()
{
int n;
cin >> n;
vector<int> u(n), v(n), w(n);
for(int i=0; i<n-1; i++) cin >> u[i];
for(int i=0; i<n-1; i++) cin >> v[i];
for(int i=0; i<n-1; i++) cin >> w[i];
vector<ll> res = minimum_closure_costs(n, u, v, w);
for(int v : res) cout << v << " ";
}
int32_t main()
{
// freopen("x.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Solve();
}*/
Compilation message
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:53:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
53 | if(adj[1].size() == n - 1)
| ~~~~~~~~~~~~~~^~~~~~~~
roads.cpp:76:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
76 | while(res.size() != n) res.pb(0);
| ~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5204 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
4 ms |
5076 KB |
Output is correct |
9 |
Correct |
4 ms |
5076 KB |
Output is correct |
10 |
Correct |
4 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
29 ms |
9936 KB |
Output is correct |
13 |
Correct |
51 ms |
13488 KB |
Output is correct |
14 |
Correct |
52 ms |
12632 KB |
Output is correct |
15 |
Correct |
59 ms |
13376 KB |
Output is correct |
16 |
Correct |
62 ms |
13460 KB |
Output is correct |
17 |
Correct |
54 ms |
13480 KB |
Output is correct |
18 |
Correct |
2 ms |
4948 KB |
Output is correct |
19 |
Correct |
44 ms |
12720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
43 ms |
12008 KB |
Output is correct |
3 |
Correct |
52 ms |
12892 KB |
Output is correct |
4 |
Correct |
48 ms |
13360 KB |
Output is correct |
5 |
Correct |
48 ms |
13424 KB |
Output is correct |
6 |
Correct |
4 ms |
5076 KB |
Output is correct |
7 |
Correct |
6 ms |
5204 KB |
Output is correct |
8 |
Correct |
4 ms |
5076 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
5008 KB |
Output is correct |
11 |
Correct |
3 ms |
5008 KB |
Output is correct |
12 |
Correct |
29 ms |
10080 KB |
Output is correct |
13 |
Correct |
55 ms |
13392 KB |
Output is correct |
14 |
Correct |
3 ms |
5012 KB |
Output is correct |
15 |
Correct |
41 ms |
12768 KB |
Output is correct |
16 |
Correct |
44 ms |
13372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
25 ms |
36304 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
516 ms |
36376 KB |
Output is correct |
5 |
Correct |
695 ms |
36388 KB |
Output is correct |
6 |
Correct |
647 ms |
36516 KB |
Output is correct |
7 |
Correct |
630 ms |
36512 KB |
Output is correct |
8 |
Correct |
679 ms |
36388 KB |
Output is correct |
9 |
Correct |
713 ms |
36516 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
4 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
5012 KB |
Output is correct |
16 |
Correct |
341 ms |
36376 KB |
Output is correct |
17 |
Correct |
680 ms |
36392 KB |
Output is correct |
18 |
Correct |
676 ms |
36400 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4964 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
25 ms |
36304 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
516 ms |
36376 KB |
Output is correct |
5 |
Correct |
695 ms |
36388 KB |
Output is correct |
6 |
Correct |
647 ms |
36516 KB |
Output is correct |
7 |
Correct |
630 ms |
36512 KB |
Output is correct |
8 |
Correct |
679 ms |
36388 KB |
Output is correct |
9 |
Correct |
713 ms |
36516 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
4 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
5012 KB |
Output is correct |
16 |
Correct |
341 ms |
36376 KB |
Output is correct |
17 |
Correct |
680 ms |
36392 KB |
Output is correct |
18 |
Correct |
676 ms |
36400 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4964 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
4948 KB |
Output is correct |
23 |
Execution timed out |
2076 ms |
36492 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
91 ms |
85260 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
91 ms |
85260 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
5204 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
4 ms |
5076 KB |
Output is correct |
9 |
Correct |
4 ms |
5076 KB |
Output is correct |
10 |
Correct |
4 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
29 ms |
9936 KB |
Output is correct |
13 |
Correct |
51 ms |
13488 KB |
Output is correct |
14 |
Correct |
52 ms |
12632 KB |
Output is correct |
15 |
Correct |
59 ms |
13376 KB |
Output is correct |
16 |
Correct |
62 ms |
13460 KB |
Output is correct |
17 |
Correct |
54 ms |
13480 KB |
Output is correct |
18 |
Correct |
2 ms |
4948 KB |
Output is correct |
19 |
Correct |
44 ms |
12720 KB |
Output is correct |
20 |
Correct |
2 ms |
4948 KB |
Output is correct |
21 |
Correct |
43 ms |
12008 KB |
Output is correct |
22 |
Correct |
52 ms |
12892 KB |
Output is correct |
23 |
Correct |
48 ms |
13360 KB |
Output is correct |
24 |
Correct |
48 ms |
13424 KB |
Output is correct |
25 |
Correct |
4 ms |
5076 KB |
Output is correct |
26 |
Correct |
6 ms |
5204 KB |
Output is correct |
27 |
Correct |
4 ms |
5076 KB |
Output is correct |
28 |
Correct |
2 ms |
4948 KB |
Output is correct |
29 |
Correct |
3 ms |
5008 KB |
Output is correct |
30 |
Correct |
3 ms |
5008 KB |
Output is correct |
31 |
Correct |
29 ms |
10080 KB |
Output is correct |
32 |
Correct |
55 ms |
13392 KB |
Output is correct |
33 |
Correct |
3 ms |
5012 KB |
Output is correct |
34 |
Correct |
41 ms |
12768 KB |
Output is correct |
35 |
Correct |
44 ms |
13372 KB |
Output is correct |
36 |
Correct |
3 ms |
4948 KB |
Output is correct |
37 |
Correct |
25 ms |
36304 KB |
Output is correct |
38 |
Correct |
3 ms |
4948 KB |
Output is correct |
39 |
Correct |
516 ms |
36376 KB |
Output is correct |
40 |
Correct |
695 ms |
36388 KB |
Output is correct |
41 |
Correct |
647 ms |
36516 KB |
Output is correct |
42 |
Correct |
630 ms |
36512 KB |
Output is correct |
43 |
Correct |
679 ms |
36388 KB |
Output is correct |
44 |
Correct |
713 ms |
36516 KB |
Output is correct |
45 |
Correct |
3 ms |
4948 KB |
Output is correct |
46 |
Correct |
3 ms |
4948 KB |
Output is correct |
47 |
Correct |
3 ms |
4948 KB |
Output is correct |
48 |
Correct |
3 ms |
4948 KB |
Output is correct |
49 |
Correct |
4 ms |
4948 KB |
Output is correct |
50 |
Correct |
3 ms |
5012 KB |
Output is correct |
51 |
Correct |
341 ms |
36376 KB |
Output is correct |
52 |
Correct |
680 ms |
36392 KB |
Output is correct |
53 |
Correct |
676 ms |
36400 KB |
Output is correct |
54 |
Correct |
3 ms |
4948 KB |
Output is correct |
55 |
Correct |
3 ms |
4964 KB |
Output is correct |
56 |
Correct |
3 ms |
4948 KB |
Output is correct |
57 |
Correct |
3 ms |
4948 KB |
Output is correct |
58 |
Execution timed out |
2076 ms |
36492 KB |
Time limit exceeded |
59 |
Halted |
0 ms |
0 KB |
- |