oj.uz

Submission #415778

# Submission time Handle Problem Language Result Execution time Memory
415778 2021-06-01T13:48:57 Z ngpin04 Džumbus (COCI19_dzumbus) C++14
110 / 110
 112 ms 12176 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e3 + 5; 
const int oo = 1e9 + 1;

vector <int> adj[N];

int dp[N][N][2][2];
int f[N][2][2];
int g[N][2][2];
int val[N];
int sz[N];
int a[N];
int n,m;

bool vis[N];

void mini(int &a, int b) {
	if (a > b) 
		a = b;
	if (a > oo)
		a = oo;
}

void dfs(int u, int p) {
	vis[u] = true;
	for (int v : adj[u]) 
		if (!vis[v])
			dfs(v, u);

	for (int i = 0; i <= n; i++)
	for (int j = 0; j < 2; j++)
	for (int k = 0; k < 2; k++)
		f[i][j][k] = g[i][j][k] = oo;

	f[0][0][0] = 0;
	f[0][1][0] = a[u];
	sz[u] = 1;
	for (int v : adj[u]) if (v != p) {
		for (int l = 0; l <= sz[u]; l++)
		for (int i = 0; i < 2; i++)
		for (int k = 0; k < 2; k++) 

		for (int r = 0; r <= sz[v]; r++) 
		for (int j = 0; j < 2; j++)
		for (int t = 0; t < 2; t++) {
			int node = l + r + (i & j) * (!k + !t);
			int used = k | (i & j);
			mini(g[node][i][used], f[l][i][k] + dp[v][r][j][t]);
		}

		sz[u] += sz[v];

		for (int l = 0; l <= sz[u]; l++)
		for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++) {
			f[l][i][j] = g[l][i][j];
			g[l][i][j] = oo;
		}
	}

	for (int i = 0; i <= sz[u]; i++)
	for (int j = 0; j < 2; j++)
	for (int k = 0; k < 2; k++)
		dp[u][i][j][k] = f[i][j][k];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	for (int i = 1; i <= m; i++) {
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	a[0] = oo;
	for (int i = 1; i <= n; i++) if (!vis[i]){
		dfs(i, -1);		
		adj[0].push_back(i);
	}
	dfs(0, -1);

	for (int i = n; i >= 0; i--) {	
		val[i] = oo;
		for (int j = 0; j < 2; j++)
		for (int k = 0; k < 2; k++)
			val[i] = min(val[i], dp[0][i][j][k]);
		if (i < m)
			val[i] = min(val[i], val[i + 1]);
	}


	int q; cin >> q;
	while (q--) {
		int x; cin >> x;
		int res = upper_bound(val, val + n + 1, x) - (val + 1);
		cout << res << "\n";
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8780 KB Output is correct
2 Correct 51 ms 9468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8780 KB Output is correct
2 Correct 51 ms 9468 KB Output is correct
3 Correct 86 ms 12176 KB Output is correct
4 Correct 108 ms 11512 KB Output is correct
5 Correct 112 ms 10812 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2760 KB Output is correct
2 Correct 46 ms 2512 KB Output is correct
3 Correct 47 ms 3020 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8780 KB Output is correct
2 Correct 51 ms 9468 KB Output is correct
3 Correct 86 ms 12176 KB Output is correct
4 Correct 108 ms 11512 KB Output is correct
5 Correct 112 ms 10812 KB Output is correct
6 Correct 41 ms 2760 KB Output is correct
7 Correct 46 ms 2512 KB Output is correct
8 Correct 47 ms 3020 KB Output is correct
9 Correct 71 ms 6704 KB Output is correct
10 Correct 84 ms 7240 KB Output is correct
11 Correct 105 ms 6852 KB Output is correct