oj.uz

Submission #1097265

# Submission time Handle Problem Language Result Execution time Memory
1097265 2024-10-06T15:34:44 Z hickwhither Džumbus (COCI19_dzumbus) C++17
20 / 110
 1000 ms 11092 KB 
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int INF = 1e9+7;
const int MAXN = 1e3+3;

int n, m, q;
struct Edge
{
    int u, v;
    Edge(){}
    Edge(int _u, int _v): u(_u), v(_v) {}
    int other(const int x){return x^u^v;}
} edge[MAXN] ;

vector<int> e[MAXN];
int s[MAXN];

#define minimize(a,b) a=min(a,b)

int dp[MAXN][MAXN][2];
int lst[MAXN][2];

void dfs(int u=1, int p=0){
    dp[u][0][0] = 0;
    dp[u][0][1] = s[u];
    
    // dp[u][1][1] = s[u]; 
    
    for(int &z: e[u]){
        int v = edge[z].other(u);
        
        if(v == p) continue;
        dfs(v, u);

        for(int i=0; i<=n; ++i)
            lst[i][0] = dp[u][i][0],
            lst[i][1] = dp[u][i][1];
        
        for(int U=0; U<=n; ++U){
            if(dp[u][U][0]>=INF && dp[u][U][1] >= INF) continue;
            for(int V=0; V<=n; ++V){
                if(dp[v][V][0]>=INF && dp[v][V][1] >= INF) continue;
                minimize(dp[u][U+V][0], lst[U][0] + dp[v][V][0]);
                minimize(dp[u][U+V][0], lst[U][0] + dp[v][V][1]);
                
                minimize(dp[u][U+V][1], lst[U][1] + dp[v][V][0]);
                minimize(dp[u][U+V][1], lst[U][1] + dp[v][V][1]);

                minimize(dp[u][U+V+1][1], lst[U][0] + dp[v][V][1] + s[u]);
                minimize(dp[u][U+V+1][1], lst[U][1] + dp[v][V][0] + s[v]);

                minimize(dp[u][U+V+2][1], lst[U][0] + dp[v][V][0] + s[u] + s[v]);
            }
        }
    }
}


signed main()
{
    cin.tie(0) -> sync_with_stdio(0);

    cin >> n >> m;
    for(int i=1; i<=n; ++i) cin >> s[i];
    for(int i=0; i<m; ++i){
        cin >> edge[i].u >> edge[i].v;
        e[edge[i].u].emplace_back(i);
        e[edge[i].v].emplace_back(i);
    }

    memset(dp, 0x3f, sizeof(dp));
    dfs();
    // cout << "***\n";

    // for(int i=1; i<=n; ++i){
    //     cout << i << "**\n";
    //     for(int j=0; j<=n; ++j) cout << dp[i][j][0] << ' '; cout << '\n';
    //     for(int j=0; j<=n; ++j) cout << dp[i][j][1] << ' '; cout << '\n';
    //     cout << '\n';
    // }
    
    cin >> q;
    while(q--){
        int x;cin >> x;
        bool fl = 1;
        for(int i=n; i>1; --i)
            if(dp[1][i][0]<=x || dp[1][i][1]<=x){
                cout << i << '\n';
                fl = 0;
                break;
            }
        if(fl) cout << "0\n";
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 8476 KB Output is correct
2 Correct 808 ms 8424 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 8476 KB Output is correct
2 Correct 808 ms 8424 KB Output is correct
3 Correct 996 ms 10588 KB Output is correct
4 Correct 621 ms 11092 KB Output is correct
5 Execution timed out 1070 ms 8540 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9052 KB Output is correct
2 Incorrect 33 ms 9800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 8476 KB Output is correct
2 Correct 808 ms 8424 KB Output is correct
3 Correct 996 ms 10588 KB Output is correct
4 Correct 621 ms 11092 KB Output is correct
5 Execution timed out 1070 ms 8540 KB Time limit exceeded
6 Halted 0 ms 0 KB -