#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define fi first
#define se second
#define pb push_back
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
using ll = long long;
using ii = pair<ll,ll>;
const int N = 1010;
const ll oo = 1e16;
int n, m; ll d[N];
vector<int> g[N];
int vis[N];
void dfs(int u, int f) {
vis[u] = 1;
for(int v : g[u]) if(v != f)
dfs(v, u);
}
vector<ll> dp[2][N], ondp[2][N];
void combine(vector<ll> &x, vector<ll> &y) {
int szx = sz(x), szy = sz(y);
vector<ll> ret(szx + szy - 1, oo);
for(int i = 0; i < szx; i++)
for(int j = 0; j < szy; j++)
ret[i + j] = min(ret[i + j], x[i] + y[j]);
x = ret;
}
void solve(int u, int f) {
for(int v : g[u]) if(v != f)
solve(v, u);
dp[0][u] = {0, oo};
dp[1][u] = {0, oo};
for(int v : g[u]) if(v != f) {
combine(dp[0][u], dp[0][v]);
combine(dp[1][u], dp[0][v]);
}
ondp[0][u] = {0, d[u]};
ondp[1][u] = {0, d[u]};
for(int v : g[u]) if(v != f) {
combine(ondp[0][u], dp[1][v]);
combine(ondp[1][u], dp[1][v]);
}
int sz = sz(dp[0][u]);
for(int i = 2; i < sz; i++) dp[0][u][i] = min(dp[0][u][i], ondp[0][u][i]);
int sz1 = sz(dp[1][u]);
for(int i = 0; i < sz1; i++) dp[1][u][i] = min(dp[1][u][i], ondp[1][u][i]);
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%lld", &d[i]);
for(int i = 0; i < m; i++) {
int u, v; scanf("%d %d", &u, &v);
g[u].pb(v); g[v].pb(u);
}
vector<int> roots;
for(int i = 1; i <= n; i++) if(!vis[i]) {
roots.pb(i); dfs(i, 0);
}
for(int u : roots) {
g[0].pb(u); g[u].pb(0);
}
solve(0, -1);
// for(int i = 0; i <= n + 1; i++)
// printf("%d: %lld\n", i, dp[0][0][i]);
int q; scanf("%d", &q);
while(q--) {
ll x; scanf("%lld", &x);
int lo = 3, hi = sz(dp[0][0]) - 1, idx = 1;
while(lo <= hi) {
int mid = lo + hi >> 1;
if(dp[0][0][mid] <= x) idx = mid, lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", idx - 1);
}
return 0;
}
Compilation message
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:89:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
89 | int mid = lo + hi >> 1;
| ~~~^~~~
dzumbus.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:67:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | for(int i = 1; i <= n; i++) scanf("%lld", &d[i]);
| ~~~~~^~~~~~~~~~~~~~~
dzumbus.cpp:69:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | int u, v; scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:84:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | int q; scanf("%d", &q);
| ~~~~~^~~~~~~~~~
dzumbus.cpp:86:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | ll x; scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
9548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
9548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
2544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
9548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
