#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
vector <int> d;
vector <vector <int> > dp0, dp1, g;
vector <bool> used;
vector <int> sz;
void dfs(int v, int p = -1)
{
used[v] = true;
int allsz = 0;
dp0[v][0] = 0;
sz[v] = 1;
int y = g[v].size();
for(int i = 0; i < y; i++)
{
int to = g[v][i];
if(to != p)
{
dfs(to, v);
sz[v] += sz[to];
for(int k = allsz; k >= 0; k--)
{
for(int j = 0; j <= sz[to]; j++)
{
if(j != 1)
{
dp0[v][k + j] = min(dp0[v][k + j], dp0[v][k] + min(dp1[to][j], dp0[to][j]));
}
}
}
allsz += sz[to];
}
}
allsz = 1;
dp1[v][1] = d[v];
for(int i = 0; i < y; i++)
{
int to = g[v][i];
if(to != p)
{
for(int k = allsz; k >= 0; k--)
{
for(int j = 1; j <= sz[to]; j++)
{
dp1[v][k + j] = min(dp1[v][k + j], dp1[v][k] + dp1[to][j]);
dp1[v][k + j] = min(dp1[v][k + j], dp1[v][k] + dp0[to][j]);
}
}
allsz += sz[to];
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
d.resize(n);
sz.resize(n);
g.resize(n);
used.resize(n);
dp0.resize(n, vector <int> (n + 1, 1e18));
dp1.resize(n, vector <int> (n + 1, 1e18));
for(int i = 0; i < n; i++)
{
cin >> d[i];
}
for(int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
}
vector <int> alldp(n + 1, 1e18);
alldp[0] = 0;
for(int i = 0; i < n; i++)
{
if(!used[i])
{
dfs(i);
for(int k = n; k >= 0; k--)
{
for(int j = 2; j <= sz[i] && k + j <= n; j++)
{
alldp[k + j] = min(alldp[j + k], alldp[k] + min(dp0[i][j], dp1[i][j]));
}
}
}
}
alldp[1] = 0;
int q;
cin >> q;
while(q--)
{
int s;
cin >> s;
int l = 0, r= n + 1;
while(r - l > 1)
{
int midd = (r + l) / 2;
if(alldp[midd] <= s)
{
l = midd;
}
else
{
r = midd;
}
}
if(l == 1)
{
l = 0;
}
cout << l << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
16256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
16256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
1272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
16256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
