oj.uz

Submission #340048

# Submission time Handle Problem Language Result Execution time Memory
340048 2020-12-26T16:18:25 Z sinamhdv Džumbus (COCI19_dzumbus) C++11
110 / 110
 177 ms 47340 KB 
// oj.uz COCI19_dzumbus
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const ll LINF = (ll)INF * INF;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod)
#define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 1100

int n, m;
vector<int> adj[MAXN];
ll dp[3][MAXN][MAXN];
int D[MAXN];
int par[MAXN];
int subtree[MAXN];

ll mdp[MAXN][MAXN];
ll ans[MAXN][MAXN];

void dfs(int v)
{
	subtree[v] = 1;
	
	// dp base
	dp[1][v][0] = D[v];
	dp[0][v][0] = 0;

	bool fr = true;

	for (int u : adj[v])
	{
		if (u == par[v])
		{
			continue;
		}
		par[u] = v;
		dfs(u);

		if (fr)
		{
			for (int i = subtree[u] + 1; i >= 2; i--)
			{
				dp[2][v][i] = min(dp[2][v][i], min(dp[2][u][i - 1], dp[1][u][i - 2]) + D[v]);
				dp[1][v][i] = min(dp[1][v][i], dp[0][u][i] + D[v]);
				dp[0][v][i] = min(dp[0][v][i], min(dp[0][u][i], min(dp[1][u][i], dp[2][u][i])));
			}
			fr = false;
			subtree[v] += subtree[u];
			continue;
		}
		
		// update dp[2]
		for (int i = subtree[v]; i >= 1; i--)
		{
			for (int j = subtree[u]; j >= 1; j--)
			{
				ll nw = min(dp[2][v][i] + min(dp[0][u][j], min(dp[1][u][j - 1], dp[2][u][j])), \
							dp[1][v][i - 1] + min(dp[1][u][j - 1], dp[2][u][j]));
				dp[2][v][i + j] = min(dp[2][v][i + j], nw);
			}
		}

		// update dp[1] & dp[0]
		for (int i = subtree[v]; i >= 0; i--)
		{
			for (int j = subtree[u]; j >= 0; j--)
			{
				dp[1][v][i + j] = min(dp[1][v][i + j], dp[1][v][i] + dp[0][u][j]);
				dp[0][v][i + j] = min(dp[0][v][i + j], dp[0][v][i] + min(dp[0][u][j], min(dp[1][u][j], dp[2][u][j])));
			}
		}

		subtree[v] += subtree[u];
	}
}

int32_t main(void)
{
	fast_io;
	cin >> n >> m;
	FOR(i, 1, n + 1)
	{
		cin >> D[i];
	}
	FOR(i, 0, m)
	{
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}

	// fill dp
	FOR(i, 0, 3)
	{
		FOR(j, 0, MAXN)
		{
			fill(dp[i][j], dp[i][j] + MAXN, LINF);
		}
	}

	vector<int> rt;
	FOR(i, 1, n + 1)
	{
		if (!par[i])
		{
			par[i] = -1;
			dfs(i);
			rt.pb(i);
		}
	}
	FOR(i, 1, n + 1)
	{
		FOR(j, 0, subtree[i] + 1)
		{
			mdp[i][j] = min(dp[0][i][j], min(dp[1][i][j], dp[2][i][j]));
		}
	}

	/*
	FOR(i, 1, n + 1)
	{
		FOR(j, 0, subtree[i] + 1)
		{
			FOR(k, 0, 3)
			{
				cout << "dp[" << k << "][" << i << "][" << j << "]: " << dp[k][i][j] << endl;
			}
		}
	}
	*/
	

	
	dbgr(rt.begin(), rt.end());


	FOR(i, 0, MAXN)
	{
		fill(ans[i], ans[i] + MAXN, LINF);
	}

	ans[0][0] = 0;
	FOR(i, 1, (int)rt.size() + 1)
	{
		ans[i][0] = 0;
		FOR(j, 1, n + 1)
		{
			FOR(k, 0, min(subtree[rt[i - 1]], j) + 1)
			{
				ans[i][j] = min(ans[i][j], ans[i - 1][j - k] + mdp[rt[i - 1]][k]);
			}
		}
		dbgr(ans[i], ans[i] + n + 1);
	}

	int q;
	cin >> q;
	while (q--)
	{
		int si;
		cin >> si;
		for (int i = n; i >= 0; i--)
		{
			if (ans[rt.size()][i] <= si)
			{
				cout << i << endl;
				break;
			}
		}
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 44524 KB Output is correct
2 Correct 30 ms 44780 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 44524 KB Output is correct
2 Correct 30 ms 44780 KB Output is correct
3 Correct 87 ms 47212 KB Output is correct
4 Correct 91 ms 47340 KB Output is correct
5 Correct 173 ms 46828 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 40940 KB Output is correct
2 Correct 62 ms 40504 KB Output is correct
3 Correct 78 ms 41068 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 44524 KB Output is correct
2 Correct 30 ms 44780 KB Output is correct
3 Correct 87 ms 47212 KB Output is correct
4 Correct 91 ms 47340 KB Output is correct
5 Correct 173 ms 46828 KB Output is correct
6 Correct 60 ms 40940 KB Output is correct
7 Correct 62 ms 40504 KB Output is correct
8 Correct 78 ms 41068 KB Output is correct
9 Correct 91 ms 44608 KB Output is correct
10 Correct 96 ms 45172 KB Output is correct
11 Correct 177 ms 44780 KB Output is correct