Submission #1185939

#TimeUsernameProblemLanguageResultExecution timeMemory
1185939icebearDžumbus (COCI19_dzumbus)C++20
110 / 110
41 ms27464 KiB
// ~~ icebear love attttt ~~ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ii> iii; template<class T> bool minimize(T &a, const T &b) { if (a > b) return a = b, true; return false; } template<class T> bool maximize(T &a, const T &b) { if (a < b) return a = b, true; return false; } #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORR(i,a,b) for(int i=(a); i>=(b); --i) #define REP(i, n) for(int i=0; i<(n); ++i) #define RED(i, n) for(int i=(n)-1; i>=0; --i) #define MASK(i) (1LL << (i)) #define BIT(S, i) (((S) >> (i)) & 1) #define mp make_pair #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() #define task "gen" #define prev love const int MOD = 1e9 + 7; const int inf = 1e9 + 27092008; const ll INF = 1e18 + 27092008; const int N = 1000 + 5; int n, m, q; ll dp[N][N][3], f[N][3], need[N]; int sz[N], ans[200005]; vector<int> G[N]; ii Q[200005]; void dfs(int u, int par) { if (sz[u]) return; sz[u] = 1; dp[u][0][0] = 0; dp[u][1][1] = need[u]; for(int v : G[u]) if (v != par) { dfs(v, u); FOR(j, 0, sz[u]) REP(k, 3) { f[j][k] = dp[u][j][k]; dp[u][j][k] = INF; } FOR(j, 0, sz[u]) REP(x, 3) FOR(k, 0, sz[v]) REP(y, 3) { if (x == 0 && y == 1) continue; // choose only v -> unsatisfied int state = x; if (x > 0 && y > 0) state = 2; // choose u and child minimize(dp[u][j + k][state], f[j][x] + dp[v][k][y]); } sz[u] += sz[v]; } } void init(void) { cin >> n >> m; FOR(i, 1, n) cin >> need[i]; FOR(i, 1, m) { int u, v; cin >> u >> v; G[u].pb(v); G[v].pb(u); } cin >> q; FOR(i, 1, q) cin >> Q[i].fi, Q[i].se = i; sort(Q + 1, Q + q + 1); } void process(void) { FOR(i, 0, n) FOR(j, 0, n + 1) REP(k, 3) dp[i][j][k] = INF; FOR(i, 1, n) if (sz[i] == 0) { dfs(i, -1); G[0].pb(i); } need[0] = INF; dfs(0, -1); vector<pair<ll, int>> best; FOR(j, 2, n) best.pb(mp(dp[0][j][0], j)); sort(all(best)); int res = 0, j = 0; FOR(i, 1, q) { while(j < n - 1 && best[j].fi <= Q[i].fi) { maximize(res, best[j].se); j++; } ans[Q[i].se] = res; } FOR(i, 1, q) cout << ans[i] << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int tc = 1; // cin >> tc; while(tc--) { init(); process(); } return 0; }

Compilation message (stderr)

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...