/*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")
//*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int ,int > pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn = 1010;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
int n , m , q;
vector < int > adj[maxn];
int d[maxn];
ll ans[maxn];
ll dp[maxn][maxn][2];
ll pd[maxn][2];
bool mark[maxn];
int sz[maxn];
const ll inf = 1e15;
void dfs(int v){
sz[v] = 1;
mark[v] = 1;
dp[v][0][1] = d[v];
dp[v][0][0] = 0;
for(auto u : adj[v])if(!mark[u]){
dfs(u);
for(int i = 0 ; i <= sz[v] + sz[u] ; i ++)
pd[i][0] = pd[i][1] = inf;
for(int i = 0 ; i <= sz[v] ; i ++){
//if(dp[v][i][0] == inf)continue;
for(int j = 0 ; j <= sz[u] ; j ++){
//if(min(dp[u][j][1] , dp[u][j][0]) == inf)continue;
pd[i+j][0] = min({pd[i+j][0] , dp[v][i+j][0] , dp[v][i][0] + min(dp[u][j][1] , dp[u][j][0])});
}
}
for(int i = 0 ; i <= sz[v] ; i ++){
//if(dp[v][i][1] == inf)continue;
for(int j = 0 ; j <= sz[u] ; j ++){
//if(min(dp[u][j][1] , dp[u][j][0]) == inf)continue;
if(i == 0 and j == 0){
pd[i+j][1] = min({pd[i+j][1] , dp[v][i+j][1] , dp[v][i][1] + dp[u][j][0]});
pd[i+j+2][1] = min({pd[i+j+2][1] , dp[v][i+j+2][1] , dp[v][i][1] + dp[u][j][1]});
continue;
}
if(i == 0){
pd[i+j][1] = min({pd[i+j][1] , dp[v][i+j][1] , dp[v][i][1] + dp[u][j][0]});
pd[i+j+1][1] = min({pd[i+j+1][1] , dp[v][i+j+1][1] , dp[v][i][1] + dp[u][j][1]});
continue;
}
if(j == 0){
pd[i+1][1] = min({pd[i + 1][1] , dp[v][i+1][1] , dp[v][i][1] + dp[u][j][1]});
pd[i][1] = min({pd[i][1] , dp[v][i][1] , dp[v][i][1] + dp[u][j][0]});
continue;
}
pd[i+j][1] = min({pd[i+j][1] , dp[v][i+j][1] , dp[v][i][1] + min(dp[u][j][1] , dp[u][j][0])});
}
}
sz[v] += sz[u];
for(int i = 0 ; i <= sz[v] ; i ++)
dp[v][i][0] = pd[i][0] , dp[v][i][1] = pd[i][1];
}
}
int x = 0;
void add(int v){
for(int i = 0 ; i <= x ; i ++)
for(int j = 0 ; j <= sz[v] ; j ++)
ans[i+j] = min(ans[i + j] , ans[i] + min(dp[v][j][1] , dp[v][j][0]));
}
int32_t main(){
migmig;
cin >> n >> m;
for(int i = 0 ; i <= n ; i ++){
ans[i] = inf;
for(int j = 0 ; j <= n ; j ++)
dp[i][j][1] = dp[i][j][0] = inf;
}
ans[0] = 0;
for(int i = 1 ; i <= n ; i ++)
cin >> d[i];
for(int i = 1 ; i <= m ; i ++){
int u , v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
for(int i = 1 ; i <= n ; i ++){
if(!mark[i])dfs(i);
add(i);
}
cin >> q;
//for(int i = 1 ; i <= n ; i ++)cout << ans[i] << ' ';
while(q -- ){
int x;
cin >> x;
int res = 0;
for(int i = 2 ; i <= n ; i ++)
if(ans[i] <= x)res = i;
cout << res << endl;
}
return(0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
16364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
16364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
3052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
16364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
