Submission #868496

#TimeUsernameProblemLanguageResultExecution timeMemory
868496phongcdDžumbus (COCI19_dzumbus)C++14
110 / 110
158 ms19028 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ull unsigned long long #define ii pair <int, int> #define ill pair <ll, ll> #define ild pair <ld, ld> #define fi first #define se second #define all(x) x.begin(), x.end() #define file "test" using namespace std; const int N = 1e3 + 5; const int M = 40; const ll MOD = 1e9 + 7; const ll INF = 3e18; const ll base = 311; const ll base2 = 1e4 + 7; const int BLOCK_SIZE = 400; int n, m; int sz[N], vis[N]; ll d[N], f[N][N][2]; vector <int> g[N]; void minimize(ll &a, ll b) { if (a > b) a = b; } void dfs(int u) { vis[u] = 1; f[u][0][0] = 0; if (u) sz[u] = 1; for (int v: g[u]) if (!vis[v]) { dfs(v); for (int i = sz[u]; i >= 0; i --) for (int j = sz[v]; j >= 0; j --) { minimize(f[u][i + j][0], f[u][i][0] + min(f[v][j][0], f[v][j][1])); minimize(f[u][i + j][1], f[u][i][1] + min(f[v][j][0], f[v][j][1])); minimize(f[u][i + j + 1][1], f[u][i][0] + f[v][j][1] + d[u]); minimize(f[u][i + j + 1][1], f[u][i][1] + f[v][j][0] + d[v]); minimize(f[u][i + j + 2][1], f[u][i][0] + f[v][j][0] + d[u] + d[v]); } sz[u] += sz[v]; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // // #ifndef ONLINE_JUDGE // freopen(file".inp","r",stdin); freopen(file".out","w",stdout); // // #endif cin >> n >> m; for (int i = 1; i <= n; i ++) cin >> d[i]; for (int i = 0; i < m; i ++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } memset(f, 0x3f, sizeof f); f[0][0][0] = 0; for (int i = 1; i <= n; i ++) if (!vis[i]) { g[0].push_back(i); dfs(0); } int q; cin >> q; while (q --) { int s; cin >> s; int x = n; for (int i = n; i >= 0; --i) { if (f[0][i][0] <= s) { x = i; break; } } cout << x << '\n'; } } /* /\_/\ zzZ (= -_-) / >u >u */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...