oj.uz

Submission #523463

# Submission time Handle Problem Language Result Execution time Memory
523463 2022-02-07T17:09:31 Z Alexandruabcde Džumbus (COCI19_dzumbus) C++14
110 / 110
 66 ms 18952 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
constexpr int NMAX = 1005;
constexpr LL INF = 1e16;

int N, M;
int D[NMAX];
LL dp[NMAX][NMAX][2];

LL aux[NMAX][2];

vector <int> G[NMAX];
bool viz[NMAX];

int Size[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 1; i <= N; ++ i )
        cin >> D[i];

    for (int i = 1; i <= M; ++ i ) {
        int x, y;
        cin >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }

    for (int i = 0; i <= N; ++ i )
        for (int j = 0; j <= N; ++ j )
            for (int k = 0; k < 2; ++ k )
                dp[i][j][k] = INF;
}

void Combine (int son, int dad) {
    for (int i = 0; i <= N; ++ i )
        for (int j = 0; j < 2; ++ j )
            aux[i][j] = INF;

    for (int k_son = 0; k_son <= Size[son]; ++ k_son) {
        for (int k_dad = 0; k_dad <= Size[dad]; ++ k_dad) {
            aux[k_son+k_dad][1] = min(aux[k_son+k_dad][1], dp[son][k_son][1] + dp[dad][k_dad][1]);
            aux[k_son+k_dad][1] = min(aux[k_son+k_dad][1], dp[son][k_son][0] + dp[dad][k_dad][1]);
            aux[k_son+k_dad][0] = min(aux[k_son+k_dad][0], dp[son][k_son][1] + dp[dad][k_dad][0]);
            aux[k_son+k_dad][0] = min(aux[k_son+k_dad][0], dp[son][k_son][0] + dp[dad][k_dad][0]);

            if (k_dad + 1 <= Size[dad])
                aux[k_son+k_dad+1][1] = min(aux[k_son+k_dad+1][1], dp[dad][k_dad][0] + D[dad] + dp[son][k_son][1]);

            if (k_son + 1 <= Size[son])
                aux[k_son+k_dad+1][1] = min(aux[k_son+k_dad+1][1], dp[dad][k_dad][1] + D[son] + dp[son][k_son][0]);

            if (k_dad + 1 <= Size[dad] && k_son + 1 <= Size[son])
                aux[k_son+k_dad+2][1] = min(aux[k_son+k_dad+2][1], dp[dad][k_dad][0] + dp[son][k_son][0] + D[son] + D[dad]);
        }
    }

    for (int i = 0; i <= N; ++ i )
        for (int j = 0; j < 2; ++ j )
            dp[dad][i][j] = min(dp[dad][i][j], aux[i][j]);
}

void Dfs (int Node, int dad = 0) {
    dp[Node][0][0] = 0;
    Size[Node] = 1;
    viz[Node] = 1;

    for (auto it : G[Node]) {
        if (it == dad) continue;

        Dfs(it, Node);
    }

    Combine(Node, dad);
    Size[dad] += Size[Node];
}

void Solve () {
    D[0] = INF;
    dp[0][0][0] = 0;
    for (int i = 1; i <= N; ++ i ) {
        if (viz[i]) continue;

        Dfs(i);
    }
}

void Write () {
    int Q;
    cin >> Q;

    for (; Q; -- Q ) {
        LL cant;
        cin >> cant;

        int st = 2, dr = N;
        int ans = 0;

        while (st <= dr) {
            int mij = (st + dr) / 2;

            if (dp[0][mij][0] <= cant) {
                ans = mij;
                st = mij + 1;
            }
            else dr = mij-1;
        }

        cout << ans << '\n';
    }
}
int main () {
    Read();
    Solve();
    Write();

    return 0;
}

Compilation message

dzumbus.cpp: In function 'void Solve()':
dzumbus.cpp:87:12: warning: overflow in conversion from 'LL' {aka 'long long int'} to 'int' changes value from '10000000000000000' to '1874919424' [-Woverflow]
   87 |     D[0] = INF;
      |            ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16180 KB Output is correct
2 Correct 16 ms 16204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16180 KB Output is correct
2 Correct 16 ms 16204 KB Output is correct
3 Correct 59 ms 18312 KB Output is correct
4 Correct 60 ms 18952 KB Output is correct
5 Correct 58 ms 18592 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2932 KB Output is correct
2 Correct 36 ms 2696 KB Output is correct
3 Correct 49 ms 3172 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16180 KB Output is correct
2 Correct 16 ms 16204 KB Output is correct
3 Correct 59 ms 18312 KB Output is correct
4 Correct 60 ms 18952 KB Output is correct
5 Correct 58 ms 18592 KB Output is correct
6 Correct 40 ms 2932 KB Output is correct
7 Correct 36 ms 2696 KB Output is correct
8 Correct 49 ms 3172 KB Output is correct
9 Correct 66 ms 18120 KB Output is correct
10 Correct 49 ms 18840 KB Output is correct
11 Correct 60 ms 18556 KB Output is correct