oj.uz

Submission #229218

# Submission time Handle Problem Language Result Execution time Memory
229218 2020-05-03T21:03:07 Z VEGAnn Džumbus (COCI19_dzumbus) C++14
110 / 110
 148 ms 19260 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define MP make_pair
#define PB push_back
#define ft first
#define sd second
#define pii pair<ll, ll>
#define sz(x) ((ll)x.size())
using namespace std;
typedef long long ll;
const ll N = 1010;
const ll oo = 1e18;
vector<ll> g[N];
ll n, siz[N], f[N][N][3], ff[N][N][3], res[N], a[N], m, rez[N];
bool mrk[N];

void calc(ll v, ll p){
	mrk[v] = 1;
	siz[v] = 1;
	
	
	for (ll u : g[v]){
		if (u == p) continue;
		calc(u, v);
		siz[v] += siz[u];
	}
	
	for (ll it = 0; it < 2; it++)
		for (ll i = 0; i <= siz[v]; i++)
			f[v][i][it] = oo;
	
	f[v][0][0] = 0;
	
	ll csz = 1;
	
	for (ll u : g[v]){
		if (u == p) continue;

		for (ll it = 0; it < 2; it++)
			for (ll i = 0; i <= csz; i++)
				ff[v][i][it] = f[v][i][it];
		
		for (ll k = 0; k <= siz[u]; k++){
				
//			cerr << u << " " << f[u][k][0] << " " << f[u][k][1] << '\n';
			ll mn = min(f[u][k][0], f[u][k][1]);
			if (mn == oo) continue;
			
			for (ll kol = csz; kol >= 0; kol--){
					
//				cerr << kol << '\n';
				
				if (ff[v][kol][0] != oo)
					f[v][kol + k][0] = min(f[v][kol + k][0], ff[v][kol][0] + mn);
				
				if (ff[v][kol][0] != oo && f[u][k][0] + a[u] < oo)
					f[v][kol + k + 2][1] = min(f[v][kol + k + 2][1], ff[v][kol][0] + f[u][k][0] + a[v] + a[u]);
					
				if (ff[v][kol][0] != oo && f[u][k][1] < oo)
					f[v][kol + k + 1][1] = min(f[v][kol + k + 1][1], ff[v][kol][0] + f[u][k][1] + a[v]);
				
				if (ff[v][kol][1] != oo)
					f[v][kol + k][1] = min(f[v][kol + k][1], ff[v][kol][1] + mn);
			
				if (ff[v][kol][1] != oo && f[u][k][0] + a[u] < oo)
					f[v][kol + k + 1][1] = min(f[v][kol + k + 1][1], ff[v][kol][1] + f[u][k][0] + a[u]);
			}
			
		}
		
		csz += siz[u];
	}
}

int main(){
	
	ios_base::sync_with_stdio(0); cin.tie(0);
	
//	freopen("in.txt","r",stdin);

	cin >> n >> m;
	
	for (ll i = 0; i < n; i++)
		cin >> a[i];
	
	for (ll i = 0; i < m; i++){
		ll x, y; cin >> x >> y;
		x--; y--;
		g[x].PB(y);
		g[y].PB(x);
	}

	fill(res, res + N, oo);
	
	res[0] = 0;
	
	for (ll i = 0; i < n; i++){
		if (mrk[i]) continue;
		calc(i, -1);
		
		for (ll i = 0; i < N; i++)
			rez[i] = res[i];
		
		for (ll k = 1; k <= siz[i]; k++)
		for (ll j = n; j - k >= 0; j--)
			if (res[j - k] != oo)
				res[j] = min(res[j], rez[j - k] + min(f[i][k][0], f[i][k][1]));
	}
	
	ll qq; cin >> qq;
	
	for (; qq; qq--){
		ll x; cin >> x;
		for (ll i = n; i >= 0; i--)
			if (res[i] <= x){
				cout << i << '\n';
				break;
			}
	}
	
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15104 KB Output is correct
2 Correct 16 ms 16128 KB Output is correct
3 Correct 78 ms 19260 KB Output is correct
4 Correct 72 ms 17788 KB Output is correct
5 Correct 148 ms 16888 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3320 KB Output is correct
2 Correct 44 ms 2936 KB Output is correct
3 Correct 61 ms 3320 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15104 KB Output is correct
2 Correct 16 ms 16128 KB Output is correct
3 Correct 78 ms 19260 KB Output is correct
4 Correct 72 ms 17788 KB Output is correct
5 Correct 148 ms 16888 KB Output is correct
6 Correct 41 ms 3320 KB Output is correct
7 Correct 44 ms 2936 KB Output is correct
8 Correct 61 ms 3320 KB Output is correct
9 Correct 67 ms 9720 KB Output is correct
10 Correct 73 ms 9696 KB Output is correct
11 Correct 146 ms 8696 KB Output is correct