/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1010;
const ll inf = 1e17;
int n, m, used[maxn], sub[maxn];
ll d[maxn];
vector < int > g[maxn];
vector < ll > dp[maxn][3];
void to_process(int v, int u)
{
vector < ll > combine[3];
///cout << v << " : " << dp[v][0].size() << " " << dp[u][0].size() << endl;
combine[0].resize(dp[v][0].size() + dp[u][0].size() + 2, inf);
combine[1].resize(dp[v][0].size() + dp[u][0].size() + 2, inf);
combine[2].resize(dp[v][0].size() + dp[u][0].size() + 2, inf);
for (int i = 0; i < dp[v][0].size(); i ++)
for (int j = 0; j < dp[u][0].size(); j ++)
combine[0][i + j] = min(combine[0][i + j], dp[v][0][i] + dp[u][0][j]);
for (int i = 0; i < dp[v][0].size(); i ++)
for (int j = 0; j < dp[u][1].size(); j ++)
combine[0][i + j] = min(combine[0][i + j], dp[v][0][i] + dp[u][1][j]);
for (int i = 0; i < dp[v][0].size(); i ++)
for (int j = 0; j < dp[u][2].size(); j ++)
combine[0][i + j] = min(combine[0][i + j], dp[v][0][i] + dp[u][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[v]);
for (int i = 0; i < dp[v][0].size(); i ++)
for (int j = 0; j < dp[u][0].size(); j ++)
{
if (i + j + 2 < combine[2].size())
{
combine[2][i + j + 2] = min(combine[2][i + j + 2], dp[v][1][i] + dp[u][1][j]);
}
if (i + j + 1 < combine[2].size())
combine[2][i + j + 1] = min(combine[2][i + j + 1], dp[v][1][i] + dp[u][2][j]);
combine[2][i + j] = min(combine[2][i + j], dp[v][2][i] + dp[u][2][j]);
//if (v == 1)
// cout << i << " " << j << " " << v << " " << u << " " << dp[v][2][i] << " " << dp[u][0][j] << endl;
if (i + j + 1 < combine[2].size())
combine[2][i + j + 1] = min(combine[2][i + j + 1], dp[v][2][i] + dp[u][1][j]);
combine[2][i + j] = min(combine[2][i + j], dp[v][2][i] + dp[u][0][j]);
}
//if (v == 1)
// cout << combine[2][5] << " ::: " << combine[2][6] << endl;
dp[v][0] = combine[0];
dp[v][1] = combine[1];
dp[v][2] = combine[2];
}
void calc_sub(int v, int par)
{
sub[v] = 1;
for (int u : g[v])
{
if (u != par)
{
calc_sub(u, v);
sub[v] += sub[u];
}
}
}
void dfs(int v)
{
//cout << "here " << v << endl;
dp[v][0] = {0};
dp[v][1] = {d[v]};
dp[v][2] = {inf};
used[v] = 1;
for (int u : g[v])
{
if (used[u])
continue;
dfs(u);
to_process(v, u);
}
}
void trav(int v)
{
used[v] = 1;
for (int u : g[v])
{
if (!used[u])
trav(u);
}
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
cin >> d[i];
for (int i = 1; i <= m; i ++)
{
int v, u;
cin >> v >> u;
g[v].push_back(u);
g[u].push_back(v);
}
vector < int > roots;
int root = 0;
for (int i = 1; i <= n; i ++)
{
if (!used[i])
{
trav(i);
g[root].push_back(i);
}
}
calc_sub(0, -1);
memset(used, 0, sizeof(used));
int ver = 8;
///cout << "dfs " << ver << endl;
dfs(0);
/**for (int type = 0; type < 3; type ++, cout << endl)
for (int j = 0; j < dp[ver][type].size(); j ++)
cout << dp[ver][type][j] << " ";*/
int q;
cin >> q;
for (int t = 0; t < q; t ++)
{
ll x;
cin >> x;
ll lf = 2, rf = n;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (dp[root][0][mf] <= x)
lf = mf + 1;
else
rf = mf - 1;
}
if (rf < 2)
cout << 0 << endl;
else
cout << rf << endl;
}
}
int main()
{
speed();
solve();
return 0;
}
Compilation message
dzumbus.cpp: In function 'void to_process(int, int)':
dzumbus.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 0; i < dp[v][0].size(); i ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int j = 0; j < dp[u][0].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (int i = 0; i < dp[v][0].size(); i ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int j = 0; j < dp[u][1].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i = 0; i < dp[v][0].size(); i ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int j = 0; j < dp[u][2].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
47 | for (int i = 0; i < min(combine[0].size(), combine[1].size()); i ++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int i = 0; i < dp[v][0].size(); i ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:52:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int j = 0; j < dp[u][0].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | if (i + j + 2 < combine[2].size())
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
dzumbus.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if (i + j + 1 < combine[2].size())
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
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 | if (i + j + 1 < combine[2].size())
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
dzumbus.cpp: In function 'void solve()':
dzumbus.cpp:142:9: warning: unused variable 'ver' [-Wunused-variable]
142 | int ver = 8;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
21460 KB |
Output is correct |
| 2 |
Correct |
33 ms |
30180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
21460 KB |
Output is correct |
| 2 |
Correct |
33 ms |
30180 KB |
Output is correct |
| 3 |
Correct |
64 ms |
28084 KB |
Output is correct |
| 4 |
Correct |
65 ms |
26624 KB |
Output is correct |
| 5 |
Correct |
64 ms |
23756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
1408 KB |
Output is correct |
| 2 |
Correct |
28 ms |
1088 KB |
Output is correct |
| 3 |
Correct |
31 ms |
892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
21460 KB |
Output is correct |
| 2 |
Correct |
33 ms |
30180 KB |
Output is correct |
| 3 |
Correct |
64 ms |
28084 KB |
Output is correct |
| 4 |
Correct |
65 ms |
26624 KB |
Output is correct |
| 5 |
Correct |
64 ms |
23756 KB |
Output is correct |
| 6 |
Correct |
30 ms |
1408 KB |
Output is correct |
| 7 |
Correct |
28 ms |
1088 KB |
Output is correct |
| 8 |
Correct |
31 ms |
892 KB |
Output is correct |
| 9 |
Correct |
61 ms |
4008 KB |
Output is correct |
| 10 |
Correct |
61 ms |
3852 KB |
Output is correct |
| 11 |
Correct |
58 ms |
3420 KB |
Output is correct |
