oj.uz

Submission #711614

# Submission time Handle Problem Language Result Execution time Memory
711614 2023-03-17T09:50:00 Z dozer Džumbus (COCI19_dzumbus) C++14
110 / 110
 68 ms 34948 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32204 KB Output is correct
2 Correct 24 ms 32160 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32204 KB Output is correct
2 Correct 24 ms 32160 KB Output is correct
3 Correct 59 ms 34424 KB Output is correct
4 Correct 62 ms 34948 KB Output is correct
5 Correct 68 ms 34496 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 33980 KB Output is correct
2 Correct 47 ms 33844 KB Output is correct
3 Correct 50 ms 34328 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32204 KB Output is correct
2 Correct 24 ms 32160 KB Output is correct
3 Correct 59 ms 34424 KB Output is correct
4 Correct 62 ms 34948 KB Output is correct
5 Correct 68 ms 34496 KB Output is correct
6 Correct 48 ms 33980 KB Output is correct
7 Correct 47 ms 33844 KB Output is correct
8 Correct 50 ms 34328 KB Output is correct
9 Correct 52 ms 34032 KB Output is correct
10 Correct 64 ms 34796 KB Output is correct
11 Correct 57 ms 34460 KB Output is correct