Submission #336468

#	Time	Username	Problem	Language	Result	Execution time	Memory
336468		parsabahrami	Džumbus (COCI19_dzumbus)	C++17	110 / 110	76 ms	19308 KiB

dzumbus

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

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 1e3 + 10; 
const ll INF = 1e18;
ll pd[2][N], dp[2][N][N], A[N], dp2[N]; int S[N], M[N], D[N], n, q, sum, m;
vector<int> adj[N];

void DFS(int v, int p = -1) {
    M[v] = 1;
    fill(dp[1][v], dp[1][v] + N, INF);
    fill(dp[0][v], dp[0][v] + N, INF);
    dp[0][v][0] = 0;
    dp[1][v][1] = D[v];
    S[v] = 1;
    for (int u : adj[v]) {
        if (u == p) continue;
        DFS(u, v);
        for (int i = 0; i <= S[v] + S[u]; i++) pd[0][i] = pd[1][i] = INF;
        for (int i = 0; i <= S[v]; i++) {
            for (int j = 0; j <= S[u]; j++) {
                pd[0][i + j] = min(pd[0][i + j], dp[0][v][i] + dp[0][u][j]);
                pd[0][i + j] = min(pd[0][i + j], dp[1][v][i] + dp[1][u][j]);
                pd[1][i + j] = min(pd[1][i + j], dp[1][v][i] + dp[0][u][j]);
                pd[1][i + j] = min(pd[1][i + j], dp[1][v][i] + dp[1][u][j]);
            }
        }
        S[v] += S[u];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j <= S[v]; j++) {
                dp[i][v][j] = min(dp[i][v][j], pd[i][j]);
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &D[i]);
    for (int i = 1; i <= m; i++) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    fill(A, A + N, INF);
    A[0] = 0;
    for (int v = 1; v <= n; v++) {
        if (M[v]) continue;
        DFS(v);
        for (int i = 0; i <= sum + S[v]; i++) dp2[i] = INF;
        for (int i = 0; i <= sum; i++) {
            for (int j = 0; j <= S[v]; j++) {
                dp2[i + j] = min(dp2[i + j], A[i] + dp[0][v][j]);
            }
        }
        sum += S[v];
        for (int i = 0; i <= sum; i++) {
            A[i] = min(A[i], dp2[i]);
        }
    }
    A[n + 1] = INF;
    for (int i = n; i >= 0; i--) {
        A[i] = min(A[i], A[i + 1]);
        //printf("%d %lld\n", i, A[i]);
    }
    for (scanf("%d", &q); q; q--) {
        int x; scanf("%d", &x); 
        printf("%ld\n", upper_bound(A, A + n + 1, x) - A - 1);
    }
    return 0;
}

Compilation message (stderr)

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
dzumbus.cpp:47:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |     for (int i = 1; i <= n; i++) scanf("%d", &D[i]);
      |                                  ~~~~~^~~~~~~~~~~~~
dzumbus.cpp:49:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |         int u, v; scanf("%d%d", &u, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~
dzumbus.cpp:74:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |     for (scanf("%d", &q); q; q--) {
      |          ~~~~~^~~~~~~~~~
dzumbus.cpp:75:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |         int x; scanf("%d", &x);
      |                ~~~~~^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30