oj.uz

Submission #1106136

# Submission time Handle Problem Language Result Execution time Memory
1106136 2024-10-29T10:52:37 Z TrendBattles Džumbus (COCI19_dzumbus) C++14
110 / 110
 52 ms 35400 KB 
#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;

#define INFILE "DZUMBUS.INP"
#define OUTFILE "DZUMBUS.OUT"

const int MAX_N = 1000;
lli dp[MAX_N + 10][MAX_N + 10][2][2];

vector <int> graph[MAX_N + 10];
int visited[MAX_N + 10];

void Trace(int u) {
    if (visited[u]) return;
    visited[u] = true;
    for (int v : graph[u]) Trace(v);
}

int cost[MAX_N + 10];
void minimise(lli& x, lli y) {
    if (x > y) x = y;
}

int subtree_size[MAX_N + 10];
void DFS(int u) {
    for (int v : graph[u]) {
        graph[v].erase(find(graph[v].begin(), graph[v].end(), u));
        DFS(v);
    }

    subtree_size[u] = 1;
    dp[u][0][0][0] = 0;
    dp[u][0][1][0] = cost[u];

    for (int v : graph[u]) {
        for (int i = subtree_size[u]; i >= 0; --i) {
            lli tmp[2][2];
            for (int c_u = 0; c_u < 2; ++c_u) {
                for (int adj_u = 0; adj_u < 2; ++adj_u) {
                    tmp[c_u][adj_u] = dp[u][i][c_u][adj_u];
                }
            }

            for (int j = 0; j <= subtree_size[v]; ++j) {
                for (int c_u = 0; c_u < 2; ++c_u) {
                    for (int adj_u = 0; adj_u < 2; ++adj_u) {
                        for (int c_v = 0; c_v < 2; ++c_v) {
                            for (int adj_v = 0; adj_v < 2; ++adj_v) {
                                int new_size = i + j;
                                if (c_u and c_v) new_size += (adj_u == 0) + (adj_v == 0);

                                minimise(dp[u][new_size][c_u][adj_u | c_v], tmp[c_u][adj_u] + dp[v][j][c_v][adj_v]);
                            }
                        }
                    }
                }
            }
        }
        subtree_size[u] += subtree_size[v];
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen(INFILE, "r")) {
        freopen(INFILE, "r", stdin);
        freopen(OUTFILE, "w", stdout);
    }

    memset(dp, 0x3f, sizeof dp);
    int N, M; cin >> N >> M;
    for (int i = 1; i <= N; ++i) cin >> cost[i];
    for (int i = 1; i <= M; ++i) {
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    visited[0] = true;
    for (int i = 1; i <= N; ++i) {
        if (visited[i]) continue;
        graph[0].push_back(i);
        graph[i].push_back(0);

        Trace(i);
    }

    DFS(0);
    vector <lli> value;
    for (int i = 0; i <= N; ++i) {
        value.push_back(min(dp[0][i][0][0], dp[0][i][0][1]));
    }

    for (int i = N - 1; i >= 0; --i) {
        value[i] = min(value[i], value[i + 1]);
    }

    int Q; cin >> Q;
    for (int qu = 1; qu <= Q; ++qu) {
        lli x; cin >> x;
        cout << upper_bound(value.begin(), value.end(), x) - value.begin() - 1 << '\n';
    }
    return 0;
}

Compilation message

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 32592 KB Output is correct
2 Correct 27 ms 32604 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 32592 KB Output is correct
2 Correct 27 ms 32604 KB Output is correct
3 Correct 50 ms 34632 KB Output is correct
4 Correct 52 ms 35400 KB Output is correct
5 Correct 48 ms 34892 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 34376 KB Output is correct
2 Correct 28 ms 34128 KB Output is correct
3 Correct 29 ms 34548 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 32592 KB Output is correct
2 Correct 27 ms 32604 KB Output is correct
3 Correct 50 ms 34632 KB Output is correct
4 Correct 52 ms 35400 KB Output is correct
5 Correct 48 ms 34892 KB Output is correct
6 Correct 25 ms 34376 KB Output is correct
7 Correct 28 ms 34128 KB Output is correct
8 Correct 29 ms 34548 KB Output is correct
9 Correct 42 ms 34376 KB Output is correct
10 Correct 47 ms 35152 KB Output is correct
11 Correct 50 ms 34888 KB Output is correct