# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
229218 |
2020-05-03T21:03:07 Z |
VEGAnn |
Džumbus (COCI19_dzumbus) |
C++14 |
|
148 ms |
19260 KB |
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define MP make_pair
#define PB push_back
#define ft first
#define sd second
#define pii pair<ll, ll>
#define sz(x) ((ll)x.size())
using namespace std;
typedef long long ll;
const ll N = 1010;
const ll oo = 1e18;
vector<ll> g[N];
ll n, siz[N], f[N][N][3], ff[N][N][3], res[N], a[N], m, rez[N];
bool mrk[N];
void calc(ll v, ll p){
mrk[v] = 1;
siz[v] = 1;
for (ll u : g[v]){
if (u == p) continue;
calc(u, v);
siz[v] += siz[u];
}
for (ll it = 0; it < 2; it++)
for (ll i = 0; i <= siz[v]; i++)
f[v][i][it] = oo;
f[v][0][0] = 0;
ll csz = 1;
for (ll u : g[v]){
if (u == p) continue;
for (ll it = 0; it < 2; it++)
for (ll i = 0; i <= csz; i++)
ff[v][i][it] = f[v][i][it];
for (ll k = 0; k <= siz[u]; k++){
// cerr << u << " " << f[u][k][0] << " " << f[u][k][1] << '\n';
ll mn = min(f[u][k][0], f[u][k][1]);
if (mn == oo) continue;
for (ll kol = csz; kol >= 0; kol--){
// cerr << kol << '\n';
if (ff[v][kol][0] != oo)
f[v][kol + k][0] = min(f[v][kol + k][0], ff[v][kol][0] + mn);
if (ff[v][kol][0] != oo && f[u][k][0] + a[u] < oo)
f[v][kol + k + 2][1] = min(f[v][kol + k + 2][1], ff[v][kol][0] + f[u][k][0] + a[v] + a[u]);
if (ff[v][kol][0] != oo && f[u][k][1] < oo)
f[v][kol + k + 1][1] = min(f[v][kol + k + 1][1], ff[v][kol][0] + f[u][k][1] + a[v]);
if (ff[v][kol][1] != oo)
f[v][kol + k][1] = min(f[v][kol + k][1], ff[v][kol][1] + mn);
if (ff[v][kol][1] != oo && f[u][k][0] + a[u] < oo)
f[v][kol + k + 1][1] = min(f[v][kol + k + 1][1], ff[v][kol][1] + f[u][k][0] + a[u]);
}
}
csz += siz[u];
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("in.txt","r",stdin);
cin >> n >> m;
for (ll i = 0; i < n; i++)
cin >> a[i];
for (ll i = 0; i < m; i++){
ll x, y; cin >> x >> y;
x--; y--;
g[x].PB(y);
g[y].PB(x);
}
fill(res, res + N, oo);
res[0] = 0;
for (ll i = 0; i < n; i++){
if (mrk[i]) continue;
calc(i, -1);
for (ll i = 0; i < N; i++)
rez[i] = res[i];
for (ll k = 1; k <= siz[i]; k++)
for (ll j = n; j - k >= 0; j--)
if (res[j - k] != oo)
res[j] = min(res[j], rez[j - k] + min(f[i][k][0], f[i][k][1]));
}
ll qq; cin >> qq;
for (; qq; qq--){
ll x; cin >> x;
for (ll i = n; i >= 0; i--)
if (res[i] <= x){
cout << i << '\n';
break;
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
15104 KB |
Output is correct |
2 |
Correct |
16 ms |
16128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
15104 KB |
Output is correct |
2 |
Correct |
16 ms |
16128 KB |
Output is correct |
3 |
Correct |
78 ms |
19260 KB |
Output is correct |
4 |
Correct |
72 ms |
17788 KB |
Output is correct |
5 |
Correct |
148 ms |
16888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
3320 KB |
Output is correct |
2 |
Correct |
44 ms |
2936 KB |
Output is correct |
3 |
Correct |
61 ms |
3320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
15104 KB |
Output is correct |
2 |
Correct |
16 ms |
16128 KB |
Output is correct |
3 |
Correct |
78 ms |
19260 KB |
Output is correct |
4 |
Correct |
72 ms |
17788 KB |
Output is correct |
5 |
Correct |
148 ms |
16888 KB |
Output is correct |
6 |
Correct |
41 ms |
3320 KB |
Output is correct |
7 |
Correct |
44 ms |
2936 KB |
Output is correct |
8 |
Correct |
61 ms |
3320 KB |
Output is correct |
9 |
Correct |
67 ms |
9720 KB |
Output is correct |
10 |
Correct |
73 ms |
9696 KB |
Output is correct |
11 |
Correct |
146 ms |
8696 KB |
Output is correct |