oj.uz

Submission #336468

# Submission time Handle Problem Language Result Execution time Memory
336468 2020-12-15T11:57:37 Z parsabahrami Džumbus (COCI19_dzumbus) C++17
110 / 110
 76 ms 19308 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16364 KB Output is correct
2 Correct 15 ms 16364 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16364 KB Output is correct
2 Correct 15 ms 16364 KB Output is correct
3 Correct 67 ms 18540 KB Output is correct
4 Correct 76 ms 19308 KB Output is correct
5 Correct 70 ms 18796 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2796 KB Output is correct
2 Correct 58 ms 3968 KB Output is correct
3 Correct 57 ms 4332 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16364 KB Output is correct
2 Correct 15 ms 16364 KB Output is correct
3 Correct 67 ms 18540 KB Output is correct
4 Correct 76 ms 19308 KB Output is correct
5 Correct 70 ms 18796 KB Output is correct
6 Correct 60 ms 2796 KB Output is correct
7 Correct 58 ms 3968 KB Output is correct
8 Correct 57 ms 4332 KB Output is correct
9 Correct 64 ms 18412 KB Output is correct
10 Correct 72 ms 19052 KB Output is correct
11 Correct 73 ms 18796 KB Output is correct