제출 #1097269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097269		hickwhither	Džumbus (COCI19_dzumbus)	C++17	50 / 110	696 ms	19036 KiB

dzumbus

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

int64_t dp[MAXN][MAXN][2];
int64_t 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 V=0; V<=n; ++V){ if(dp[v][V][0]>=INF && dp[v][V][1] >= INF) continue;
        for(int U=n; U>=0; --U){ if(dp[u][U][0]>=INF && dp[u][U][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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30