oj.uz

Submission #198132

# Submission time Handle Problem Language Result Execution time Memory
198132 2020-01-24T19:17:37 Z ZwariowanyMarcin Džumbus (COCI19_dzumbus) C++14
110 / 110
 115 ms 35124 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define LL long long
#define ld double
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define boost cin.tie(0), ios_base::sync_with_stdio(0);


using namespace std;

const int nax = 1010;
const LL INF = 1e18;

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

int n, m;
int cost[nax];
int a, b;
int q;
vector <int> v[nax];
bool odw[nax];

LL dp[nax][nax][2][2];
LL dp2[nax][2][2];
int siz[nax];

void dfs(int u, int p) {
	odw[u] = 1;
	siz[u] = 1;
	
	dp[u][0][0][0] = 0;
	dp[u][1][1][1] = cost[u];
	
	for (auto it : v[u])
		if (it != p) {
			dfs(it, u);
			
			for (int i = 0; i <= n; ++i)
				for (int j = 0; j < 2; ++j)
					for (int g = 0; g < 2; ++g)
						dp2[i][j][g] = INF;
						
			for (int i = 0; i <= siz[u]; ++i)
				for (int j = 0; j <= siz[it]; ++j)
					for (int x = 0; x < 2; ++x)
						for (int y = 0; y < 2; ++y)
							for (int z = 0; z < 2; ++z)
								for (int g = 0; g < 2; ++g) {
									int s = i + j - (z == 1 && g == 1 && x == 0);
									int p = (y == 1 && z == 0);
									mini(dp2[s][x][p], dp[u][i][x][y] + dp[it][j][z][g]);
								}
			siz[u] += siz[it];					
								
			for (int i = 0; i <= siz[u]; ++i)
				for (int j = 0; j < 2; ++j)
					for (int g = 0; g < 2; ++g)
						dp[u][i][j][g] = dp2[i][j][g];
		}	
}
	
LL ans[nax];	
LL ans2[nax];	

vector <pair<LL, int>> vec;

int pref[nax];			

int main() {
	scanf ("%d%d", &n, &m);
	
	for (int i = 1; i <= n; ++i)
		scanf ("%d", cost + i);
	
	for (int i = 1; i <= m; ++i) {
		scanf ("%d%d", &a, &b);
		v[a].pb(b);
		v[b].pb(a);
	}
	
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j <= n; ++j)
			for (int k = 0; k < 2; ++k)
				for (int f = 0; f < 2; ++f)
					dp[i][j][k][f] = INF;
	
	for (int i = 1; i <= n; ++i)
		ans[i] = INF;
	
	for (int i = 1; i <= n; ++i)
		if (!odw[i]) {
			dfs(i, 0);
			
			for (int j = 0; j <= n; ++j)
				ans2[j] = ans[j];
			
			for (int j = 2; j <= siz[i]; ++j)
				for (int g = n - j; 0 <= g; --g)
					ans2[g + j] = min(ans2[g + j], ans[g] + min(dp[i][j][1][0], dp[i][j][0][0]));
			
			for (int j = 0; j <= n; ++j)
				ans[j] = ans2[j];
		}
		
	for (int i = 0; i <= n; ++i)
		vec.pb({ans[i], i});
	
	sort(vec.begin(), vec.end());
	
	for (int i = 0; i < ss(vec); ++i) {
		if (i) pref[i] = pref[i - 1];
		pref[i] = max(pref[i], vec[i].se);
	}
	
	scanf ("%d", &q);
	for (int i = 1; i <= q; ++i) {
		scanf ("%d", &a);
		int ind = (int) (upper_bound(vec.begin(), vec.end(), mp(1LL * a, n + 1)) - vec.begin()) - 1;
		printf ("%d\n", pref[ind]);
	}
	
	return 0;
}

Compilation message

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &m);
  ~~~~~~^~~~~~~~~~~~~~~~
dzumbus.cpp:80:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", cost + i);
   ~~~~~~^~~~~~~~~~~~~~~~
dzumbus.cpp:83:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &a, &b);
   ~~~~~~^~~~~~~~~~~~~~~~
dzumbus.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &q);
  ~~~~~~^~~~~~~~~~
dzumbus.cpp:124:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &a);
   ~~~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 32376 KB Output is correct
2 Correct 59 ms 32248 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 32376 KB Output is correct
2 Correct 59 ms 32248 KB Output is correct
3 Correct 112 ms 34424 KB Output is correct
4 Correct 114 ms 35124 KB Output is correct
5 Correct 115 ms 34656 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3192 KB Output is correct
2 Correct 53 ms 3112 KB Output is correct
3 Correct 60 ms 3448 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 32376 KB Output is correct
2 Correct 59 ms 32248 KB Output is correct
3 Correct 112 ms 34424 KB Output is correct
4 Correct 114 ms 35124 KB Output is correct
5 Correct 115 ms 34656 KB Output is correct
6 Correct 55 ms 3192 KB Output is correct
7 Correct 53 ms 3112 KB Output is correct
8 Correct 60 ms 3448 KB Output is correct
9 Correct 88 ms 34248 KB Output is correct
10 Correct 89 ms 34808 KB Output is correct
11 Correct 89 ms 34552 KB Output is correct