Submission #870838

#TimeUsernameProblemLanguageResultExecution timeMemory
870838underwaterkillerwhaleDžumbus (COCI19_dzumbus)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define rep(i,m,n) for(int i=m; i<=n; i++) #define reb(i,m,n) for(int i=m; i>=n; i--) #define iter(id, v) for (auto id : v) #define ii pair<int,int> #define fs first #define se second #define pb push_back #define SZ(v) (int)v.size() #define ALL(v) v.begin(), v.end() #define bit(msk, i) ((msk >> i) & 1) #define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); #define el cout <<"\n" template<typename A, typename B> ostream& operator<<(ostream& out, const pair<A, B> &v) { out << "(" << v.fs <<"," << v.se << ") "; return out; } #ifndef ONLINE_JUDGE #include "debug.h" #else #define deb(...) 23 #define ___ #define n____ #endif mt19937 rd(chrono :: steady_clock :: now().time_since_epoch().count()); ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); } const ll N = 1e3 + 7; const ll Mod = 1e9 + 7; const ll bse = 137; const ll szBL = 650; const ll INF = 1e18; int n, m, Q; ll D[N]; vector<int> ke[N]; int subtree[N]; int dd[N]; ll dp[N][N][2], f[N][N][2]; int nn; ll pre[N]; ii qr[N]; inline void minimize(ll &a, ll b) { if (a > b) a = b; } void dfs (int u, int pa) { vector<int> Ch = {0}; subtree[u] = 1, dd[u] = 1; iter (&v, ke[u]) { if (v != pa) { // deb(u, v); dfs(v, u); subtree[u] += subtree[v]; Ch.pb(v); } } int nC = SZ(Ch) - 1; rep (i, 0, nC) { deb(u, Ch[i]); } rep (i, 0, nC) rep (j, 0, subtree[u]) { f[i][j][0] = f[i][j][1] = INF; } int tot = 1; f[0][0][0] = 0; f[0][0][1] = D[u]; rep (i, 1, nC) { int &curC = Ch[i]; rep (k, 0, tot) rep (t, 0, subtree[curC]) { minimize(f[i][k + t][0], f[i - 1][k][0] + min(dp[curC][t][1], dp[curC][t][0])); if (k) { minimize(f[i][k + t][1], f[i - 1][k - 1][0] + dp[curC][t][1] + D[u]); if (t) { minimize(f[i][k + t][1], f[i - 1][k - 1][0] + dp[curC][t - 1][0] + D[curC] + D[u]); } } f[i][k + t][1] = min({f[i][k + t][1], f[i - 1][k][1] + dp[curC][t][1], f[i - 1][k][1] + dp[curC][t][0]}); if (t) { minimize(f[i][k + t][1], f[i - 1][k][1] + dp[curC][t - 1][0] + D[curC]); } } tot += subtree[curC]; } rep (k, 0, subtree[u]) { dp[u][k][0] = f[nC][k][0]; dp[u][k][1] = f[nC][k][1]; } } void chloe_solution() { cin >> n >> m; D[0] = INF; rep (i, 1, n) cin >> D[i]; rep (i, 1, m) { ll u, v; cin >> u >> v; ke[u].pb(v); ke[v].pb(u); } rep (i, 1, n) { if (dd[i] == 0) { dfs(i, 0); ke[0].pb(i); ke[i].pb(0); } } dfs(0, 0); reb (i, n, 0) { minimize(dp[0][i][0], dp[0][i + 1][0]); } cin >> Q; rep (qi, 1, Q) { cin >> qr[qi].fs; qr[qi].se = qi; } sort (qr + 1, qr + 1 + Q); vector<int> ans(Q + 2); ll cur = 0; rep (qi, 1, Q) { while (cur <= n && dp[0][cur][0] <= qr[qi].fs) ++cur; ans[qr[qi].se] = cur - 1; } rep (i, 1, Q) cout << ans[i] <<"\n"; } int main() { // file("c"); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll num_Test = 1; // cin >> num_Test; while(num_Test--) chloe_solution(); } /* */

Compilation message (stderr)

dzumbus.cpp:22:14: fatal error: debug.h: No such file or directory
   22 |     #include "debug.h"
      |              ^~~~~~~~~
compilation terminated.