Submission #871831

#	Time	Username	Problem	Language	Result	Execution time	Memory
871831		MisterReaper	Džumbus (COCI19_dzumbus)	C++17	50 / 110	38 ms	19092 KiB

dzumbus

//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64

int dp[1005][1005][2];
 
#define ONLINE_JUDGE
void solve() {
    fill_n(&dp[0][0][0], 1005 * 1005 * 2, int(1E18));
 
    int n, m;
    cin >> n >> m;
 
    vector <int> vec(n +1);
    for(int i = 1; i <= n; i++)
        cin >> vec[i];
        
    vector <int> adj[n +1];
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
 
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    
    int start = 0;
    for(int i = 1; i <= n; i++) {
        if(int(adj[i].size()) == 1) {
            start = i;
        }
    }
    
    vector <int> order;
    function <void(int, int)> dfs = [&](int node, int par) -> void {
        order.emplace_back(node);
        for(int &child : adj[node]) {
            if(child != par) 
                dfs(child, node);
        }
    };
 
    dfs(start, -1);

    dp[0][0][0] = 0;
    for(int i = 1; i < n; i++) {
        int u = order[i];
        for(int j = 0; j <= n; j++) {
            dp[i][j][0] = min(dp[i -1][j][0], dp[i -1][j][1]);
            dp[i][j + 1][1] = min(dp[i][j +1][1], dp[i -1][j][1] + vec[u]);
            dp[i][j + 2][1] = min(dp[i][j +2][1], dp[i -1][j][0] + vec[u] + vec[order[i -1]]);
        }
    }

    for(int i = 0; i < 2; i++) {
        for(int j = n; j >= 0; j--) {
            dp[n -1][j][i] = min(dp[n -1][j][i], dp[n -1][j +1][i]);
        }
    }
 
    int q;
    cin >> q;
 
    while(q--) {
        int s;
        cin >> s;
 
        int l = 0, r = n, ans = 0;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(min(dp[n -1][mid][0], dp[n -1][mid][1]) <= s) {
                l = mid +1;
                ans = mid;
            } else {
                r = mid -1;
            }
        }

        cout << ans << "\n";
    }
    
    return;
}
 
signed main() {
    #ifndef ONLINE_JUDGE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int t = 1; //cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }
 
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30