#define _FORTIFY_SOURCE 0
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define vi vector<ll>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<ll, ll>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
#define base complex<ld>
using namespace std;
const ll INF = (ll)2e9;
const ll inf = (ll)1e18;
const ld eps = (ld)1e-12;
const ll mod = (ll)1e9 + 7;
const ll p = 31;
const ll mod2 = (ll)1e9 + 7;
const ll MAXN = (ll)1000 + 3;
const ll MAXC = (ll)1e6 + 11;
const ll MAXE = (ll)100;
const ll MAXLOG = (ll)19;
const ll asci = (ll)256;
const ll block = 31623;
const ld PI = acos(-1LL);
const ld e = 2.7182818284;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<
// pii,
// null_type,
// less<pii>,
// rb_tree_tag,
// tree_order_statistics_node_update>
// ordered_set;
ll int_rand() {
if (RAND_MAX == (1LL << 15) - 1LL) {
return (rand() << 15) + rand();
}
return rand();
}
ll ll_rand() {
return ((ll)int_rand() << 30LL) + int_rand();
}
istream& operator >>(istream &in, pii &x) {
cin >> x.first >> x.second;
return in;
}
template <class T>
istream& operator >>(istream &in, vector<T> &arr){
for (T &cnt : arr) {
in >> cnt;
}
return in;
}
ll dp[MAXN][MAXN];
ll dp_h[MAXN][MAXN][2];
ll dp_take[MAXN][MAXN][2];
ll ans[MAXN];
ll sz[MAXN];
vi graph[MAXN];
ll cost[MAXN];
ll used[MAXN];
void dp_calc(ll v, ll p = -1) {
dp_h[v][0][0] = cost[v];
dp[v][0] = 0;
if ((p == -1 && graph[v].size() == 0) || (p != -1 && graph[v].size() <= 1)) {
sz[v] = 1;
return;
}
dp_take[v][0][0] = 0;
for (ll u : graph[v]) {
if (p == u) continue;
dp_calc(u, v);
for (ll ws = sz[v] + sz[u]; ws > -1; --ws) {
for (ll w1 = min(0LL, ws - sz[u]); w1 <= ws; ++w1) {
ll w2 = ws - w1;
mn(dp[v][w1 + w2], dp[v][w1] + dp[u][w2]);
mn(dp_take[v][w1 + w2][1], dp_take[v][w1][1] + min({dp[u][w2], dp_h[u][max(w2 - 1, 0LL)][0], dp_h[u][w2][1]}));
mn(dp_take[v][w1 + w2][1], dp_take[v][w1][0] + min(dp_h[u][max(w2 - 1, 0LL)][0], dp_h[u][w2][1]));
mn(dp_take[v][w1 + w2][0], dp_take[v][w1][0] + dp[u][w2]);
}
}
sz[v] += sz[u];
}
++sz[v];
for (ll w = 0; w <= sz[v]; ++w) {
for (ll c = 0; c < 2; ++c) {
mn(dp_h[v][w + c][c], dp_take[v][w][c] + cost[v]);
mn(dp[v][w + c], dp_h[v][w + c][c]);
}
}
}
void solve() {
for (ll i = 0; i < MAXN; ++i) {
ans[i] = inf;
for (ll k = 0; k < 2; ++k) {
for (ll j = 0; j < MAXN; ++j) {
dp_h[i][j][0] = inf;
dp_h[i][j][1] = inf;
dp_take[i][j][0] = inf;
dp_take[i][j][1] = inf;
dp[i][j] = inf;
}
}
}
ll n, m; cin >> n >> m;
for (ll i = 0; i < n; ++i) cin >> cost[i];
for (ll i = 0; i < m; ++i) {
ll v, u; cin >> v >> u;
--v, --u;
graph[v].push_back(u);
graph[u].push_back(v);
}
vi headers;
for (ll i = 0; i < n; ++i) {
if (!sz[i]) {
dp_calc(i);
headers.push_back(i);
}
}
ans[0] = 0;
ll sz_ans = 0;
for (ll i : headers) {
for (ll ws = sz_ans + sz[i]; ws > -1; --ws) {
for (ll w = max(0LL, ws - sz[i]); w <= ws; ++w) {
mn(ans[ws], dp[i][ws - w] + ans[w]);
}
}
sz_ans += sz[i];
}
ll q; cin >> q;
while (q--) {
ll d; cin >> d;
cout << upper_bound(ans, ans + MAXN, d) - ans - 1 << "\n";
}
}
signed main() {
srand(time(0LL));
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#endif
cout.precision(30);
solve();
return 0LL;
}
Compilation message
dzumbus.cpp:1: warning: "_FORTIFY_SOURCE" redefined
1 | #define _FORTIFY_SOURCE 0
|
<built-in>: note: this is the location of the previous definition
dzumbus.cpp:25:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
25 | #pragma GCC optimize("-fwhole-program")
| ^
dzumbus.cpp:32:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize("-fstrict-overflow")
| ^
dzumbus.cpp:34:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
34 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
dzumbus.cpp:48:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
48 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/gthr.h:148,
from /usr/include/c++/9/ext/atomicity.h:35,
from /usr/include/c++/9/bits/ios_base.h:39,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from dzumbus.cpp:51:
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:102:1: error: option("tune=") was already specified
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:102:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:103:1: error: option("tune=") was already specified
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:103:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:104:1: error: option("tune=") was already specified
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:104:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:106:1: error: option("tune=") was already specified
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:106:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:107:1: error: option("tune=") was already specified
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:107:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:108:1: error: option("tune=") was already specified
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:108:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:109:1: error: option("tune=") was already specified
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:109:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:110:1: error: option("tune=") was already specified
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:110:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:112:1: error: option("tune=") was already specified
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:112:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:114:1: error: option("tune=") was already specified
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:114:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:116:1: error: option("tune=") was already specified
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:116:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:117:1: error: option("tune=") was already specified
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:117:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:119:1: error: option("tune=") was already specified
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:119:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:121:1: error: option("tune=") was already specified
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:121:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:122:1: error: option("tune=") was already specified
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:122:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:123:1: error: option("tune=") was already specified
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:123:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:125:1: error: option("tune=") was already specified
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:125:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:126:1: error: option("tune=") was already specified
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:126:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:127:1: error: option("tune=") was already specified
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:127:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:128:1: error: option("tune=") was already specified
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:128:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:129:1: error: option("tune=") was already specified
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:129:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:130:1: error: option("tune=") was already specified
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:130:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:132:1: error: option("tune=") was already specified
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:132:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:133:1: error: option("tune=") was already specified
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:133:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:134:1: error: option("tune=") was already specified
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:134:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:135:1: error: option("tune=") was already specified
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:135:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:136:1: error: option("tune=") was already specified
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:136:1: error: option("tune=") was already specified
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:237:1: error: option("tune=") was already specified
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/9/bits/gthr-default.h:237:1: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:71:3: error: option("tune=") was already specified
71 | _GLIBCXX_GTHRW(rwlock_rdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:71:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:72:3: error: option("tune=") was already specified
72 | _GLIBCXX_GTHRW(rwlock_tryrdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:72:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:73:3: error: option("tune=") was already specified
73 | _GLIBCXX_GTHRW(rwlock_wrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:73:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:74:3: error: option("tune=") was already specified
74 | _GLIBCXX_GTHRW(rwlock_trywrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:74:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:75:3: error: option("tune=") was already specified
75 | _GLIBCXX_GTHRW(rwlock_unlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/9/shared_mutex:75:3: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:89:4: error: option("tune=") was already specified
89 | __gthrw(pthread_rwlock_timedrdlock);
| ^~~~~~~
/usr/include/c++/9/shared_mutex:89:4: error: option("tune=") was already specified
/usr/include/c++/9/shared_mutex:99:4: error: option("tune=") was already specified
99 | __gthrw(pthread_rwlock_timedwrlock);
| ^~~~~~~
/usr/include/c++/9/shared_mutex:99:4: error: option("tune=") was already specified
dzumbus.cpp:96:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
96 | ll int_rand() {
| ^
dzumbus.cpp:96:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:96:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:96:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:103:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
103 | ll ll_rand() {
| ^
dzumbus.cpp:103:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:103:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:103:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:107:41: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
107 | istream& operator >>(istream &in, pii &x) {
| ^
dzumbus.cpp:107:41: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:107:41: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:107:41: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:113:49: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
113 | istream& operator >>(istream &in, vector<T> &arr){
| ^
dzumbus.cpp:113:49: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:113:49: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:113:49: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:129:29: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
129 | void dp_calc(ll v, ll p = -1) {
| ^
dzumbus.cpp:129:29: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:129:29: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:129:29: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:160:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
160 | void solve() {
| ^
dzumbus.cpp:160:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:160:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:160:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:205:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
205 | signed main() {
| ^
dzumbus.cpp:205:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:205:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
dzumbus.cpp:205:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
