Submission #711614

#	Time	Username	Problem	Language	Result	Execution time	Memory
711614		dozer	Džumbus (COCI19_dzumbus)	C++14	110 / 110	68 ms	34948 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 1005
#define int long long

const int modulo = 1e9 + 7, INF = 1e18 + 7;

int dp[2][2][N][N], arr[N], done[N], ans[N], sz[N];
vector<int> adj[N];


void mini(int &a, int b)
{
	a = min(a, b);
}

void dfs(int node, int root)
{
	done[node] = 1;
	for (auto i : adj[node]) if (i != root) dfs(i, node);
}


void f(int node, int root)
{
	dp[0][0][node][0] = 0, dp[1][1][node][1] = 0, dp[1][1][node][0] = 0;
	sz[node] = 1;
	for (auto i :adj[node])
	{
		if (i == root) continue;
		f(i, node);

		int dp2[2][2][sz[node] + sz[i] + 5];
		for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) for (int l = 0; l < sz[node] + sz[i] + 5; l++) dp2[j][k][l] = INF;

		for (int j = 0; j <= sz[node]; j++)
		{
			for (int k = 0; k <= sz[i]; k++)
			{
				mini(dp2[0][0][j + k], dp[0][0][node][j] + min(dp[0][0][i][k], dp[0][1][i][k]));
				mini(dp2[0][1][j + k + 1], dp[0][0][node][j] + dp[1][1][i][k] + arr[node] + arr[i]);
				mini(dp2[0][1][j + k], dp[0][1][node][j] + min(dp[1][1][i][k] + arr[i], dp[0][0][i][k]));
				mini(dp2[1][1][j + k], dp[1][1][node][j] + min(dp[1][1][i][k] + arr[i], dp[0][0][i][k]));
			}
		}
		for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) for (int l = 0; l < sz[node] + sz[i] + 5; l++) mini(dp[j][k][node][l], dp2[j][k][l]);
		sz[node] += sz[i];
	}
/*
	for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) 
	{
		cout<<node<<sp<<j<<sp<<k<<" : "<<endl;
		for (int l = 0; l <= sz[node]; l++) cout<<dp[j][k][node][l]<<sp;
		cout<<endl;
	}
	*/
}


int32_t main()
{
	fastio();

	for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for(int k = 0; k < N; k++) for (int l = 0; l < N; l++) dp[i][j][k][l] = INF;
	int n, m;
	cin>>n>>m;
	for (int i = 1; i <= n; i++)
		cin>>arr[i];

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


	for (int i = 1; i <= n; i++)
	{
		if (done[i] == 0)
		{
			dfs(i, 0);
			adj[0].pb(i);
		}
	}

	arr[0] = INF;
	f(0, 0);
	vector<int> v;
	for (int i = 0; i <= n; i++)
	{
		//cout<<dp[0][0][0][i]<<sp;
		v.pb(dp[0][0][0][i]);
	}
	//cout<<endl;

	int q;
	cin>>q;
	while(q--)
	{
		int tmp;
		cin>>tmp;
		int pos = upper_bound(v.begin(), v.end(), tmp) - v.begin();
		cout<<pos - 1<<endl;
	}


	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

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