oj.uz

Submission #871647

# Submission time Handle Problem Language Result Execution time Memory
871647 2023-11-11T08:31:52 Z vjudge1 Džumbus (COCI19_dzumbus) C++17
20 / 110
 30 ms 16732 KB 
//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int dp[1005][1005][2];

#define ONLINE_JUDGE
void solve() {
    fill_n(&dp[0][0][0], 1005 * 1005 * 2, -1000);

    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);
    
    for(int i = 0; i <= 1000; i++)
        dp[0][i][0] = 0;
        
    for(int i = 1; i < n; i++) {
        int u = order[i];
        for(int j = 0; j <= 1000; j++) {
            dp[i][j][0] = max(dp[i -1][j][0], dp[i -1][j][1]);

            if(j - vec[u] >= 0) {
                dp[i][j][1] = max(dp[i][j][1], dp[i -1][j - vec[u]][1] +1);
            } 
            if(j - vec[u] - vec[order[i -1]] >= 0) {
                dp[i][j][1] = max(dp[i][j][1], dp[i -1][j - vec[u] - vec[order[i -1]]][0] +2);
            }
        }
    }

    int q;
    cin >> q;

    while(q--) {
        int s;
        cin >> s;

        cout << max(dp[n -1][s][0], dp[n -1][s][1]) << "\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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8280 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8280 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Runtime error 14 ms 16732 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8280 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Runtime error 14 ms 16732 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -