oj.uz

Submission #1097282

# Submission time Handle Problem Language Result Execution time Memory
1097282 2024-10-06T16:05:35 Z hickwhither Džumbus (COCI19_dzumbus) C++17
50 / 110
 192 ms 80976 KB 
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

#define int int64_t // fuck my self

const int INF = 1e18+7;
const int MAXN = 2222;

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)

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

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

        for(int i=0; i<=sz[u]; ++i)
            lst[i][0] = dp[u][i][0],
            lst[i][1] = dp[u][i][1];
        
        for(int U=0; U<=sz[u]; ++U){
        for(int V=0; V<=sz[v]&&U+V<=n; ++V){
                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]); // u off
                minimize(dp[u][U+V+1][1], lst[U][1] + dp[v][V][0] + s[v]); // v off

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

        sz[u]=min(sz[u]+sz[v],n);
    }
}


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 43 ms 77904 KB Output is correct
2 Correct 42 ms 77908 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 77904 KB Output is correct
2 Correct 42 ms 77908 KB Output is correct
3 Correct 89 ms 80148 KB Output is correct
4 Correct 86 ms 80976 KB Output is correct
5 Correct 192 ms 80212 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 79700 KB Output is correct
2 Incorrect 68 ms 79460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 77904 KB Output is correct
2 Correct 42 ms 77908 KB Output is correct
3 Correct 89 ms 80148 KB Output is correct
4 Correct 86 ms 80976 KB Output is correct
5 Correct 192 ms 80212 KB Output is correct
6 Correct 57 ms 79700 KB Output is correct
7 Incorrect 68 ms 79460 KB Output isn't correct
8 Halted 0 ms 0 KB -