Submission #1276448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276448		chanhchuong123	Džumbus (COCI19_dzumbus)	C++20	110 / 110	39 ms	17176 KiB

dzumbus

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

const bool multiTest = false;
#define task "C"
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define BIT(mask, i) ((mask) >> (i) & 1)

template<typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) a = b; else return 0; return 1;
}
template<typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) a = b; else return 0; return 1;
}

const int oo = 1e9 + 7;
const int MAX = 1010;
int N, M, Q, D[MAX];
vector<int> adj[MAX];
int dp[MAX][MAX][2][2];

bool used[MAX];
int res[MAX];
int sz[MAX];

void preDfs(int u) {
    used[u] = true; for (int v: adj[u]) if (!used[v]) preDfs(v);
}

void dfs(int u, int p) {
    for (int a = 0; a <= N; ++a) for (int b = 0; b < 2; ++b) for (int c = 0; c < 2; ++c) dp[u][a][b][c] = oo;
    dp[u][0][1][0] = D[u];
    dp[u][0][0][0] = 0;
    sz[u] = 1;
    for (int v: adj[u]) if (v != p) {
        dfs(v, u);
        for (int d = sz[u]; d >= 0; --d) for (int e = 0; e < 2; ++e) for (int f = 0; f < 2; ++f) if (dp[u][d][e][f] != oo) {
            for (int a = 0; a <= sz[v]; ++a) for (int b = 0; b < 2; ++b) for (int c = 0; c < 2; ++c) if (dp[v][a][b][c] != oo) {
                minimize(dp[u][a + d + (b && e) * (!c + !f)][e][f | (b && e)], dp[u][d][e][f] + dp[v][a][b][c]);
            }
        }
        sz[u] += sz[v];
    }
}

void process(void) {
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        cin >> D[i];
    }
    for (int i = 1; i <= M; ++i) {
        int A, B; cin >> A >> B;
        adj[A].push_back(B);
        adj[B].push_back(A);
    }
    for (int i = 1; i <= N; ++i) if (!used[i]) {
        preDfs(i);
        adj[i].push_back(0);
        adj[0].push_back(i);
    }
    dfs(0, -1);
    for (int i = N; i >= 0; --i) {
        res[i] = dp[0][i][0][0];
        if (i < N) minimize(res[i], res[i + 1]);
    }

    cin >> Q; while (Q--) {
        int S; cin >> S;
        int l = 0, r = N + 1;
        while (r - l > 1) {
            int mid = l + r >> 1;
            if (res[mid] <= S) l = mid; else r = mid;
        }
        cout << l << '\n';
    }
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r",  stdin);
		freopen(task".out", "w", stdout);
	}

	int nTest = 1; if (multiTest) cin >> nTest;
	while (nTest--) {
		process();
	}

	return 0;
}

Compilation message (stderr)

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:85:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |                 freopen(task".inp", "r",  stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:86:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |                 freopen(task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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