oj.uz

답안 #923097

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923097 2024-02-06T15:08:13 Z a_l_i_r_e_z_a Džumbus (COCI19_dzumbus) C++17
20 / 110
 33 ms 23480 KB 
// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
// typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define int long long    
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 1000 + 100;
const ll inf = 1e18 + 7;
ll n, m, dp[maxn][maxn][2], tmp[maxn][2], cnt[maxn], a[maxn], ans[maxn];
bool mark[maxn];
vector<int> adj[maxn];

void pre_dfs(int v){
    mark[v] = 1;
    for(auto u: adj[v]){
        if(!mark[u]) pre_dfs(u);
    }
}

void dfs(int v, int p){
    cnt[v] = 1;
    for(auto u: adj[v]){
        if(u == p) continue;
        dfs(u, v);
        for(int i = 0; i <= cnt[u] + cnt[v]; i++) tmp[i][0] = tmp[i][1] = inf;
        for(int i = 0; i <= cnt[v]; i++){
            for(int j = 0; j <= cnt[u]; j++){
                if(i == 0){
                    if(j < 2) continue;
                    smin(tmp[i + j][0], min(dp[u][j][0], dp[u][j][1]));
                }
                else if(i == 1) continue;
                else{
                    if(j == 0) smin(tmp[i][0], dp[v][i][0]);
                    else if(j == 1) continue;
                    else{
                        smin(tmp[i + j][0], dp[v][i][0] + min(dp[u][j][0], dp[u][j][1]));
                    }
                }
            }
        }
        for(int i = 0; i <= cnt[v]; i++){
            for(int j = 0; j <= cnt[u]; j++){
                if(i == 0) continue;
                else if(i == 1){
                    if(j == 0) continue;
                    else if(j == 1) smin(tmp[i + j][1], a[v] + a[u]);
                    else{
                        smin(tmp[i + j][1], a[v] + dp[u][j][1]);
                        if(j > 2) smin(tmp[i + j][1], a[v] + a[u] + dp[u][j - 1][0]);
                    }
                }
                else{
                    if(j == 0) smin(tmp[i][1], dp[v][i][1]);
                    if(j == 1){
                        smin(tmp[i + j][1], dp[v][i][1] + a[u]);
                        if(i > 2) smin(tmp[i + j][1], a[u] + a[v] + dp[v][i - 1][0]);
                    }
                    else{
                        smin(tmp[i + j][1], dp[v][i][1] + min(dp[u][j][1], dp[u][j][0]));
                        if(j > 2) smin(tmp[i + j][1], dp[v][i][1] + a[u] + dp[u][j - 1][0]);
                        if(i > 2) smin(tmp[i + j][1], dp[v][i - 1][0] + a[v] + dp[u][j][1]);
                        if(i > 2 && j > 2){
                            int x = dp[v][i - 1][0] + dp[u][j - 1][0] + a[v] + a[u];
                            smin(tmp[i + j][1], x);
                        }
                    }
                }
            }
            for(int j = 3; j <= cnt[u]; j++){
                if(i == 0) continue;
                if(i == 1) smin(tmp[i + j][1], a[v] + a[u] + dp[u][j - 1][0]);
                smin(tmp[i + j][1], dp[v][i][1] + a[u] + dp[u][j - 1][0]);
            }
        }
        cnt[v] += cnt[u];
        for(int i = 0; i <= cnt[v]; i++){
            dp[v][i][0] = tmp[i][0];
            dp[v][i][1] = tmp[i][1];
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i <= n + 10; i++) for(int j = 0; j <= n + 10; j++) dp[i][j][0] = dp[i][j][1] = inf;
    for(int i = 1; i <= n; i++) cin >> a[i];
    a[n + 1] = inf;
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int i = 1; i <= n; i++) if(!mark[i]){
        pre_dfs(i);
        adj[n + 1].pb(i);
    }
    dfs(n + 1, -1);
    int q; cin >> q;
    vector<pll> vec;
    for(int i = 0; i < q; i++){
        int x; cin >> x;
        vec.pb(mp(x, i));
    }
    sort(all(vec));
    reverse(all(vec));
    int cur = n;
    for(int i = 0; i < q; i++){
        while(cur >= 2 && dp[n + 1][cur][0] > vec[i].F) cur--;
        if(cur >= 2) ans[vec[i].S] = cur;
    }
    for(int i = 0; i < q; i++){
        if(ans[i] < 0) while(true){};
        cout << ans[i] << '\n';
    }

    // dfs(1, -1);
    // cout << dp[1][6][0] << '\n';
    // // for(int i = 1; i <= n; i++){
    // //     for(int j = 0; j <= n; j++){
    // //         cout << i << ' ' << j << ' ' << dp[i][j][0] << ' ' << dp[i][j][1] << '\n';
    // //     }
    // // }

    return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 19032 KB Output is correct
2 Correct 8 ms 19292 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 19032 KB Output is correct
2 Correct 8 ms 19292 KB Output is correct
3 Incorrect 33 ms 23480 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 7372 KB Output is correct
2 Correct 26 ms 8400 KB Output is correct
3 Incorrect 28 ms 7376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 19032 KB Output is correct
2 Correct 8 ms 19292 KB Output is correct
3 Incorrect 33 ms 23480 KB Output isn't correct
4 Halted 0 ms 0 KB -