oj.uz

Submission #978525

# Submission time Handle Problem Language Result Execution time Memory
978525 2024-05-09T09:53:05 Z Beerus13 Džumbus (COCI19_dzumbus) C++14
110 / 110
 38 ms 19060 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 1e3 + 5;
const ll inf = 1e18;

bool minimize(auto &a, auto b) {
    if(a <= b) return true;
    a = b;
    return false;
}

int n, m, q, d[N], sz[N];
bool vs[N];
ll dp[2][N][N];
// 0 : don't use u
vector<int> g[N];

void dfs(int u, int p = 0) {
    vs[u] = 1;
    sz[u] = 1;
    dp[0][u][0] = 0;
    for(int v : g[u]) if(!vs[v]) {
        dfs(v, u);
    }
    for(int i = sz[p]; i >= 0; --i) {
        for(int j = 0; j <= sz[u]; ++j) {
            minimize(dp[0][p][i + j], dp[0][p][i] + min(dp[0][u][j], dp[1][u][j]));
            minimize(dp[1][p][i + j], dp[1][p][i] + min(dp[0][u][j], dp[1][u][j]));
            if(i + 1 <= sz[p]) 
                minimize(dp[1][p][i + j + 1], dp[0][p][i] + d[p] + dp[1][u][j]);
            if(j + 1 <= sz[u]) 
                minimize(dp[1][p][i + j + 1], dp[1][p][i] + d[u] + dp[0][u][j]);
            if(i + 1 <= sz[p] && j + 1 <= sz[u]) 
                minimize(dp[1][p][i + j + 2], dp[0][p][i] + d[p] + d[u] + dp[0][u][j]);
        }
    }
    sz[p] += sz[u];
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> d[i];
    for(int i = 1, u, v; i <= m; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0] = 0;
    for(int i = 1; i <= n; ++i) if(!vs[i]) dfs(i);
    for(int i = n - 1; i >= 0; --i) minimize(dp[0][0][i], dp[0][0][i + 1]);
    cin >> q;
    while(q--) {
        int lim; cin >> lim;
        int l = 0, r = n, res = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            if(dp[0][0][mid] <= lim) res = mid, l = mid + 1;
            else r = mid - 1;
        }
        cout << res << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

Compilation message

dzumbus.cpp:8:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | bool minimize(auto &a, auto b) {
      |               ^~~~
dzumbus.cpp:8:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | bool minimize(auto &a, auto b) {
      |                        ^~~~
dzumbus.cpp: In function 'void solve()':
dzumbus.cpp:59:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |             int mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16220 KB Output is correct
2 Correct 6 ms 16420 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16220 KB Output is correct
2 Correct 6 ms 16420 KB Output is correct
3 Correct 34 ms 18520 KB Output is correct
4 Correct 36 ms 19060 KB Output is correct
5 Correct 35 ms 18768 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 18260 KB Output is correct
2 Correct 29 ms 18004 KB Output is correct
3 Correct 34 ms 18512 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16220 KB Output is correct
2 Correct 6 ms 16420 KB Output is correct
3 Correct 34 ms 18520 KB Output is correct
4 Correct 36 ms 19060 KB Output is correct
5 Correct 35 ms 18768 KB Output is correct
6 Correct 36 ms 18260 KB Output is correct
7 Correct 29 ms 18004 KB Output is correct
8 Correct 34 ms 18512 KB Output is correct
9 Correct 32 ms 18296 KB Output is correct
10 Correct 36 ms 18940 KB Output is correct
11 Correct 38 ms 18772 KB Output is correct