/**
____ ____ ____ ____ ____ ____
||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 = 1e18;
int n, m, used[maxn];
ll d[maxn];
vector < int > g[maxn];
vector < ll > dp[maxn][3];
void to_process(int v, int u)
{
vector < ll > combine[3];
combine[0] = dp[v][0];
combine[1] = dp[v][1];
combine[2] = dp[v][2];
for (int i = 0; i < dp[v][0].size(); i ++)
for (int j = 0; j < dp[v][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[v][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[v][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 <= n; i ++)
combine[1][i] = min(combine[1][i], combine[0][i] + d[v]);
for (int i = 0; i <= n; i ++)
for (int j = 0; j <= n - i; j ++)
{
combine[2][i + j + 2] = min(combine[2][i + j + 2], dp[v][1][i] + dp[u][1][j]);
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;
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 dfs(int v)
{
///cout << "here " << v << endl;
dp[v][0].resize(n + 3, inf);
dp[v][1].resize(n + 3, inf);
dp[v][2].resize(n + 3, inf);
dp[v][0][0] = 0;
dp[v][1][0] = d[v];
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);
}
}
memset(used, 0, sizeof(used));
int ver = 0;
///cout << "dfs " << ver << endl;
dfs(0);
///cout << dp[1][2][3] << endl;
//for (int type = 0; type < 3; type ++, cout << endl)
//for (int j =0; j <= 10; j ++)
// cout << dp[ver][type][j] << " ";
//exit(0);
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:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int i = 0; i < dp[v][0].size(); i ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:37:27: 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 j = 0; j < dp[v][0].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int i = 0; i < dp[v][0].size(); i ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:40:27: 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 j = 0; j < dp[v][1].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i = 0; i < dp[v][0].size(); i ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:43:27: 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 j = 0; j < dp[v][2].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp: In function 'void solve()':
dzumbus.cpp:123:9: warning: unused variable 'ver' [-Wunused-variable]
123 | int ver = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1094 ms |
15828 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1094 ms |
15828 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
1392 KB |
Output is correct |
| 2 |
Correct |
35 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
37 ms |
1032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1094 ms |
15828 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
