oj.uz

Submission #998158

# Submission time Handle Problem Language Result Execution time Memory
998158 2024-06-13T10:54:02 Z Peter2017 Džumbus (COCI19_dzumbus) C++14
110 / 110
 33 ms 26968 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pill pair<int,ll>
#define mem(a, b) memset(a, b, sizeof(a))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define name "test"

using namespace std;

const int N = 1e3 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;

template <typename T1, typename T2> bool maxi(T1 &a, T2 b){if (a < b){a = b; return 1;} return 0;}
template <typename T1, typename T2> bool mini(T1 &a, T2 b){if (a > b){a = b; return 1;} return 0;}

int n;
int m;
int q;
int a[N];
int cnt[N];
ll g[N][3];
ll f[N][N][3];
ll dp[N];
bool vst[N];
vector<int> adj[N];

void load(){
    cin.tie(0)->sync_with_stdio(0);
    if (fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
}

void input(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cin >> q;
}

void merge_node(int u, int v){
    for (int i = 0; i <= cnt[u] + cnt[v] + 2; i++)
        for (int x = 0; x < 3; x++)
            g[i][x] = oo;
//    cout << f[u][0][2] << ' ' << f[u][0][1] << ' ' << f[v][0][1] << '\n';
//    if (u == 1 && v == 3){
//
//    }
    for (int i = 0; i <= cnt[u]; i++)
        for (int j = 0; j <= cnt[v]; j++){
            for (int x = 0; x < 3; x++){
                mini(g[i + j][0], f[u][i][0] + f[v][j][x]);
                mini(g[i + j][1], f[u][i][1] + f[v][j][x]);
                mini(g[i + j][2], f[u][i][2] + f[v][j][x]);
            }
            mini(g[i + j + 2][2], f[u][i][1] + f[v][j][1]);
            mini(g[i + j + 1][2], f[u][i][1] + f[v][j][2]);
            mini(g[i + j + 1][2], f[u][i][2] + f[v][j][1]);
        }
//    cout << g[2][2] << '\n';
    cnt[u] += cnt[v];
    for (int i = cnt[u]; i >= 0; i--)
        for (int x = 0; x < 3; x++){
            mini(f[u][i][x], g[i][x]);
            if (i < cnt[u]) mini(f[u][i][x], f[u][i + 1][x]);
        }
}

void dfs(int u, int pre){
    vst[u] = 1;
    cnt[u] = 1;
    f[u][0][0] = 0;
    f[u][0][1] = a[u];
    for (int v : adj[u]) if (v != pre){
        dfs(v, u);
        merge_node(u, v);
//        exit(0);
    }
}

void solve(){
    mem(f, 0x3f);
    vector<int> root;
    mem(dp, 0x3f);
    dp[0] = 0;
    int sum = 0;
    for (int i = 1; i <= n; i++){
        if (!vst[i]){
            dfs(i, 0);
            for (int j = cnt[i]; j >= 0; j--){
                mini(f[i][j][0], f[i][j][1]);
                mini(f[i][j][0], f[i][j][2]);
                if (j < cnt[i]) mini(f[i][j][0], f[i][j + 1][0]);
            }
            sum += cnt[i];
            for (int j = sum; j >= 0; j--){
                for (int k = 1; k <= cnt[i]; k++){
                    if (j >= k){
                        mini(dp[j], dp[j - k] + f[i][k][0]);
                    }
                }
            }
        }
    }
//    for (int x = 2; x < 3; x++){
//        for (int i = 0; i <= 45; i++)
//            cout << f[1][i][x] << ' ';
//        cout << '\n';
//    }
//    for (int i = 1; i <= n; i++) cout << dp[i] << ' '; cout << '\n';
    while (q--){
        ll S; cin >> S;
        int ans = 0;
        int l = 0;
        int r = n;
        while (l <= r){
            int m = (l + r) >> 1;
            if (dp[m] <= S){
                maxi(ans, m);
                l = m + 1;
            } else r = m - 1;
        }
        cout << ans << '\n';
    }
}

int main(){
    load();
    input();
    solve();
}

Compilation message

dzumbus.cpp: In function 'void load()':
dzumbus.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24156 KB Output is correct
2 Correct 10 ms 24156 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24156 KB Output is correct
2 Correct 10 ms 24156 KB Output is correct
3 Correct 32 ms 26332 KB Output is correct
4 Correct 33 ms 26968 KB Output is correct
5 Correct 32 ms 26696 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 26192 KB Output is correct
2 Correct 24 ms 25948 KB Output is correct
3 Correct 30 ms 26452 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24156 KB Output is correct
2 Correct 10 ms 24156 KB Output is correct
3 Correct 32 ms 26332 KB Output is correct
4 Correct 33 ms 26968 KB Output is correct
5 Correct 32 ms 26696 KB Output is correct
6 Correct 24 ms 26192 KB Output is correct
7 Correct 24 ms 25948 KB Output is correct
8 Correct 30 ms 26452 KB Output is correct
9 Correct 25 ms 26192 KB Output is correct
10 Correct 27 ms 26740 KB Output is correct
11 Correct 27 ms 26708 KB Output is correct