Submission #978525

#	Time	Username	Problem	Language	Result	Execution time	Memory
978525		Beerus13	Džumbus (COCI19_dzumbus)	C++14	110 / 110	38 ms	19060 KiB

dzumbus

#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 (stderr)

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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30