Submission #704798

#TimeUsernameProblemLanguageResultExecution timeMemory
704798becaidoDžumbus (COCI19_dzumbus)C++17
110 / 110
487 ms10844 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,popcnt,sse4,abm") #include <bits/stdc++.h> using namespace std; #ifdef WAIMAI #define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE) void dout() {cout << '\n';} template<typename T, typename...U> void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);} #else #define debug(...) 7122 #endif #define ll long long #define Waimai ios::sync_with_stdio(false), cin.tie(0) #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++) #define pb emplace_back #define F first #define S second const int SIZE = 1005; const ll INF = 1e18; int n, m, q; int a[SIZE]; bool vs[SIZE]; vector<ll> dp[SIZE][2], ans; vector<int> adj[SIZE]; void Merge(vector<ll> &A, vector<ll> &B, vector<ll> &C, vector<ll> &D, int wv, int wson) { int sA = A.size() - 1, sB = B.size() - 1, sC = C.size() - 1, sD = D.size() - 1; auto updA = [&](int i, ll x) { while (A.size() <= i) A.pb(INF); A[i] = min(A[i], x); }; auto updB = [&](int i, ll x) { while (B.size() <= i) B.pb(INF); B[i] = min(B[i], x); }; for (int i = sB + max(sC, sD) + 1; i >= 0; i--) { for (int j = 0; j <= sC; j++) { if (i - j <= sB && i - j >= 0) updB(i, B[i - j] + C[j]); if (i - j - 1 >= 0 && i - j - 1 <= sB) updB(i, B[i - j - 1] + C[j] + wson); } for (int j = 0; j <= sD && i - j >= 0; j++) if (i - j <= sB) updB(i, B[i - j] + D[j]); } FOR (i, 0, sA) FOR (j, 0, sC) updB(i + j + 2, A[i] + C[j] + wv + wson); FOR (i, 0, sA) FOR (j, 0, sD) updB(i + j + 1, A[i] + D[j] + wv); for (int i = sA + max(sC, sD); i >= 0; i--) { for (int j = 0; j <= sC && i - j >= 0; j++) if (i - j <= sA) updA(i, A[i - j] + C[j]); for (int j = 0; j <= sD && i - j >= 0; j++) if (i - j <= sA) updA(i, A[i - j] + D[j]); } } void Merge(vector<ll> &A, vector<ll> &C, vector<ll> &D) { int sA = A.size() - 1, sC = C.size() - 1, sD = D.size() - 1; auto updA = [&](int i, ll x) { while (A.size() <= i) A.pb(INF); A[i] = min(A[i], x); }; for (int i = sA + max(sC, sD); i >= 0; i--) { for (int j = 0; j <= sC && i - j >= 0; j++) if (i - j <= sA) updA(i, A[i - j] + C[j]); for (int j = 0; j <= sD && i - j >= 0; j++) if (i - j <= sA) updA(i, A[i - j] + D[j]); } } void dfs(int pos) { vs[pos] = 1; dp[pos][0].resize(1, 0); dp[pos][1].resize(1, INF); for (int np : adj[pos]) if (!vs[np]) { dfs(np); Merge(dp[pos][0], dp[pos][1], dp[np][0], dp[np][1], a[pos], a[np]); } } void solve() { cin >> n >> m; FOR (i, 1, n) cin >> a[i]; while (m--) { int a, b; cin >> a >> b; adj[a].pb(b); adj[b].pb(a); } ans.resize(1, 0); FOR (i, 1, n) if (!vs[i]) { dfs(i); Merge(ans, dp[i][0], dp[i][1]); } ans.resize(n + 1, INF); for (int i = n - 1; i >= 0; i--) ans[i] = min(ans[i], ans[i + 1]); cin >> q; while (q--) { int x; cin >> x; cout << upper_bound(ans.begin(), ans.end(), x) - ans.begin() - 1 << '\n'; } } int main() { Waimai; solve(); }

Compilation message (stderr)

dzumbus.cpp: In lambda function:
dzumbus.cpp:34:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         while (A.size() <= i) A.pb(INF);
      |                ~~~~~~~~~^~~~
dzumbus.cpp: In lambda function:
dzumbus.cpp:38:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |         while (B.size() <= i) B.pb(INF);
      |                ~~~~~~~~~^~~~
dzumbus.cpp: In lambda function:
dzumbus.cpp:59:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         while (A.size() <= i) A.pb(INF);
      |                ~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...