#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define lwb lower_bound
#define upb upper_bound
#define TASKNAME "NAME"
void init()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout);
}
const int SZ = 1e6+5;
const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18;
const double epsilon = 1e-3;
int n,m,q;
ll a[SZ];
vector<int> adj[SZ];
bool vis[SZ];
vector<ll> dp[SZ][3];
void preDfs(int u)
{
vis[u] = true;
for(int v : adj[u])
{
if(vis[v]) continue;
preDfs(v);
}
}
void dfs(int u, int pre)
{
dp[u][0] = {0,INFLL};
dp[u][1] = {a[u], INFLL};
dp[u][2] = {INFLL, INFLL};
for(int v : adj[u])
{
if(v == pre) continue;
dfs(v, u);
ll s = dp[u][0].size() + dp[v][0].size() - 1;
vector<ll> t0(s, INFLL), t1(s, INFLL), t2(s, INFLL);
for(int i = 0; i < dp[u][0].size(); i++)
{
for(int j = 0; j < dp[v][0].size(); j++)
{
t0[i+j] = min(t0[i+j], dp[u][0][i] + min({ dp[v][0][j], dp[v][1][j], dp[v][2][j] }));
t1[i+j] = min(t1[i+j], dp[u][1][i] + dp[v][0][j]);
t2[i+j] = min(t2[i+j], dp[u][2][i] + min(dp[v][2][j], dp[v][0][j]));
if(i + j + 1 < t2.size()) t2[i + j + 1] = min({ t2[i+j+1], dp[u][2][i] + dp[v][1][j], dp[u][1][i] + dp[v][2][j] });
if(i + j + 2 < t2.size()) t2[i+j+2] = min(t2[i+j+2], dp[u][1][i] + dp[v][1][j]);
}
}
dp[u][0] = t0;
dp[u][1] = t1;
dp[u][2] = t2;
}
}
int main()
{
init();
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
for(int i = 1; i <= m; i++)
{
int u,v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
a[0] = INFLL;
for(int i = 1; i <= n; i++)
{
if(vis[i]) continue;
preDfs(i);
adj[0].pb(i);
}
dfs(0,0);
cin >> q;
while(q--)
{
ll s;
cin >> s;
int pos = upb(dp[0][0].begin()+2, dp[0][0].end(),s) - dp[0][0].begin() - 1;
if(pos == 1) pos--;
cout << pos << '\n';
}
}
Compilation message
dzumbus.cpp: In function 'void dfs(int, int)':
dzumbus.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i = 0; i < dp[u][0].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:57:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int j = 0; j < dp[v][0].size(); j++)
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:62:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | if(i + j + 1 < t2.size()) t2[i + j + 1] = min({ t2[i+j+1], dp[u][2][i] + dp[v][1][j], dp[u][1][i] + dp[v][2][j] });
| ~~~~~~~~~~^~~~~~~~~~~
dzumbus.cpp:63:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if(i + j + 2 < t2.size()) t2[i+j+2] = min(t2[i+j+2], dp[u][1][i] + dp[v][1][j]);
| ~~~~~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
104016 KB |
Output is correct |
| 2 |
Incorrect |
38 ms |
106072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
104016 KB |
Output is correct |
| 2 |
Incorrect |
38 ms |
106072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
97872 KB |
Output is correct |
| 2 |
Incorrect |
55 ms |
97616 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
104016 KB |
Output is correct |
| 2 |
Incorrect |
38 ms |
106072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
