Submission #523463

#	Time	Username	Problem	Language	Result	Execution time	Memory
523463		Alexandruabcde	Džumbus (COCI19_dzumbus)	C++14	110 / 110	66 ms	18952 KiB

dzumbus

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

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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30