#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const long long inf = 1e18;
int n, m;
bool visited[maxn];
int subtree_size[maxn];
long long d[maxn];
vector<int> g[maxn];
vector<long long> dp[maxn][3];
void dfs_trav(int node)
{
visited[node] = true;
for (auto next_node : g[node])
{
if (visited[next_node] == false)
{
dfs_trav(next_node);
}
}
}
void dfs_subtree(int node, int par)
{
subtree_size[node] = 1;
for (auto next_node : g[node])
{
if (next_node != par)
{
dfs_subtree(next_node, node);
subtree_size[next_node] += subtree_size[node];
}
}
}
void to_combine(int node, int child)
{
vector<long long> combine[3];
combine[0].resize(dp[node][0].size() + dp[child][0].size() + 2, inf);
combine[1].resize(dp[node][0].size() + dp[child][0].size() + 2, inf);
combine[2].resize(dp[node][0].size() + dp[child][0].size() + 2, inf);
for (int i = 0; i < dp[node][0].size(); ++i)
{
for (int j = 0; j < dp[child][0].size(); ++j)
{
combine[0][i + j] = min(combine[0][i + j], dp[node][0][i] + dp[child][0][j]);
}
}
for (int i = 0; i < dp[node][0].size(); ++i)
{
for (int j = 0; j < dp[child][1].size(); ++j)
{
combine[0][i + j] = min(combine[0][i + j], dp[node][0][i] + dp[child][1][j]);
}
}
for (int i = 0; i < dp[node][0].size(); ++i)
{
for (int j = 0; j < dp[child][2].size(); ++j)
{
combine[0][i + j] = min(combine[0][i + j], dp[node][0][i] + dp[child][2][j]);
}
}
for (int i = 0; i < min(combine[0].size(), combine[1].size()); ++i)
{
combine[1][i] = min(combine[1][i], combine[0][i] + d[node]);
}
for (int i = 0; i < dp[node][0].size(); ++i)
{
for (int j = 0; j < dp[child][0].size(); ++j)
{
if (i + j + 2 < combine[2].size())
{
combine[2][i + j + 2] = min(combine[2][i + j + 2], dp[node][1][i] + dp[child][1][j]);
}
if (i + j + 1 < combine[2].size())
{
combine[2][i + j + 1] = min(combine[2][i + j + 1], dp[node][1][i] + dp[child][2][j]);
}
combine[2][i + j] = min(combine[2][i + j], dp[node][2][i] + dp[child][2][j]);
if (i + j + 1 < combine[2].size())
{
combine[2][i + j + 1] = min(combine[2][i + j + 1], dp[node][2][i] + dp[child][1][j]);
}
combine[2][i + j] = min(combine[2][i + j], dp[node][2][i] + dp[child][0][j]);
}
}
dp[node][0] = combine[0];
dp[node][1] = combine[1];
dp[node][2] = combine[2];
}
void dfs(int node)
{
dp[node][0] = {0};
dp[node][1] = {d[node]};
dp[node][2] = {inf};
visited[node] = true;
for (auto next_node : g[node])
{
if (visited[next_node] == false)
{
dfs(next_node);
to_combine(node, next_node);
}
}
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
cin >> d[i];
}
for (int i = 1; i <= m; ++i)
{
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
int root = 0;
for (int i = 1; i <= n; ++i)
{
if (visited[i] == false)
{
dfs_trav(i);
g[0].push_back(i);
}
}
dfs_subtree(0, -1);
for (int i = 1; i <= n; ++i)
{
visited[i] = false;
}
dfs(0);
int q;
cin >> q;
for (int i = 1; i <= q; ++i)
{
long long x;
cin >> x;
int l = 2;
int r = n;
while (l <= r)
{
int mid = (l + r) / 2;
if (dp[root][0][mid] <= x)
{
l = mid + 1;
}
else
{
r = mid - 1;
}
}
if (r < 2)
{
cout << 0 << "\n";
}
else
{
cout << r << "\n";
}
}
return 0;
}
Compilation message
dzumbus.cpp: In function 'void to_combine(int, int)':
dzumbus.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i = 0; i < dp[node][0].size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int j = 0; j < dp[child][0].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int i = 0; i < dp[node][0].size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int j = 0; j < dp[child][1].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i = 0; i < dp[node][0].size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:72:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int j = 0; j < dp[child][2].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
78 | for (int i = 0; i < min(combine[0].size(), combine[1].size()); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i = 0; i < dp[node][0].size(); ++i)
| ~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int j = 0; j < dp[child][0].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | if (i + j + 2 < combine[2].size())
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
dzumbus.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | if (i + j + 1 < combine[2].size())
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
dzumbus.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | if (i + j + 1 < combine[2].size())
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
29 ms |
30224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
29 ms |
30224 KB |
Output is correct |
| 3 |
Correct |
54 ms |
27948 KB |
Output is correct |
| 4 |
Correct |
61 ms |
26676 KB |
Output is correct |
| 5 |
Correct |
59 ms |
23756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
2716 KB |
Output is correct |
| 2 |
Correct |
28 ms |
2348 KB |
Output is correct |
| 3 |
Correct |
30 ms |
2764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
29 ms |
30224 KB |
Output is correct |
| 3 |
Correct |
54 ms |
27948 KB |
Output is correct |
| 4 |
Correct |
61 ms |
26676 KB |
Output is correct |
| 5 |
Correct |
59 ms |
23756 KB |
Output is correct |
| 6 |
Correct |
32 ms |
2716 KB |
Output is correct |
| 7 |
Correct |
28 ms |
2348 KB |
Output is correct |
| 8 |
Correct |
30 ms |
2764 KB |
Output is correct |
| 9 |
Correct |
55 ms |
4088 KB |
Output is correct |
| 10 |
Correct |
56 ms |
3920 KB |
Output is correct |
| 11 |
Correct |
53 ms |
3400 KB |
Output is correct |
