oj.uz

Submission #981044

# Submission time Handle Problem Language Result Execution time Memory
981044 2024-05-12T18:17:52 Z hqminhuwu Džumbus (COCI19_dzumbus) C++14
110 / 110
 37 ms 15188 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

const int N = 1e3 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7; // 998244353;

int dp[N][3][N], d[N], sz[N], ans[N];
vector <int> a[N];

void minz (int &u, int v){
	if (u > v) 
		u = v;
}

void dfs (int u, int p){
	dp[u][0][0] = 0;
	dp[u][1][1] = d[u];
	sz[u] = 1;

	for (int v : a[u])
	if (v != p){
		dfs(v, u);
		ford (i, sz[u], 0)
		forr (j, 0, sz[v]){
			minz(dp[u][0][i + j], dp[u][0][i] + dp[v][0][j]);
			minz(dp[u][1][i + j], dp[u][1][i] + dp[v][0][j]);
			minz(dp[u][2][i + j], min(dp[u][1][i] + min(dp[v][1][j], dp[v][2][j]), 
									  dp[u][2][i] + min(dp[v][0][j], min(dp[v][1][j], dp[v][2][j]))));
		}
		sz[u] += sz[v];
		forr (i, 0, sz[u]){
			minz(dp[u][1][i], dp[u][2][i]);
			minz(dp[u][0][i], dp[u][2][i]);
		}
	}
}

int n, m, q, u, v;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	#ifdef hqm
		freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
	#endif

	cin >> n >> m;

	forr (i, 1, n)
		cin >> d[i];
	
	forr (i, 1, m){
		cin >> u >> v;
		a[u].pb(v);
		a[v].pb(u);
	}

	memset (dp, 63, sizeof dp);
	memset (ans, 63, sizeof ans);

	int cur = 0;
	ans[0] = 0;

	forr (i, 1, n)
	if (dp[i][0][0]){
		dfs(i, i);
		ford (j, cur, 0)
		ford (k, sz[i], 0)
			minz(ans[j + k], ans[j] + dp[i][0][k]);
		cur += sz[i];
	}


	cin >> q;

	while (q--){
		cin >> u;
		int k = upper_bound(ans + 1, ans + 1 + n, u) - ans - 1;
		cout << k << "\n";
	}


	return 0;
}
/*



*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12376 KB Output is correct
2 Correct 5 ms 12376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12376 KB Output is correct
2 Correct 5 ms 12376 KB Output is correct
3 Correct 34 ms 14424 KB Output is correct
4 Correct 35 ms 15188 KB Output is correct
5 Correct 34 ms 14672 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 14160 KB Output is correct
2 Correct 31 ms 14160 KB Output is correct
3 Correct 31 ms 14676 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12376 KB Output is correct
2 Correct 5 ms 12376 KB Output is correct
3 Correct 34 ms 14424 KB Output is correct
4 Correct 35 ms 15188 KB Output is correct
5 Correct 34 ms 14672 KB Output is correct
6 Correct 27 ms 14160 KB Output is correct
7 Correct 31 ms 14160 KB Output is correct
8 Correct 31 ms 14676 KB Output is correct
9 Correct 30 ms 14428 KB Output is correct
10 Correct 37 ms 15072 KB Output is correct
11 Correct 32 ms 14612 KB Output is correct