oj.uz

Submission #312457

# Submission time Handle Problem Language Result Execution time Memory
312457 2020-10-13T11:06:31 Z colazcy Džumbus (COCI19_dzumbus) C++17
110 / 110
 77 ms 22264 KB 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e3 + 100;
typedef long long ll;
inline int read(){
	int x = 0;char c = getchar();
	while(!isdigit(c))c = getchar();
	while(isdigit(c))x = x * 10 + c - '0',c = getchar();
	return x;
}
int n,m,val[maxn],vis[maxn],siz[maxn];
vector<int> G[maxn];
inline void addedge(int u,int v){G[u].push_back(v);}
int f[maxn][maxn][2][2],ans[maxn];
template <typename A,typename B>
inline void chk(A &a,B b){
	if(b >= 0x3f3f3f3f)b = 0x3f3f3f3f;
	if(b < a)a = b;
} 
inline void dfs(int u){
	siz[u] = 1;
	vis[u] = 1;
	f[u][0][1][0] = val[u];
	f[u][0][0][0] = 0;
	for(int i = 0;i < G[u].size();i++){
		int v = G[u][i];
		if(vis[v])continue;
		dfs(v);
		for(int du = siz[u];du >= 0;du--)
			for(int optu1 = 0;optu1 < 2;optu1++)
				for(int optu2 = 0;optu2 < 2;optu2++)
					if(f[u][du][optu1][optu2] < 0x3f3f3f3f)
						for(int dv = 0;dv <= siz[v];dv++)
							for(int optv1 = 0;optv1 < 2;optv1++)
								for(int optv2 = 0;optv2 < 2;optv2++)
									chk(f[u][du + dv + (!optu2 + !optv2) * (optu1 && optv1)][optu1][optu2 || (optu1 && optv1)],f[u][du][optu1][optu2] + f[v][dv][optv1][optv2]);
		siz[u] += siz[v];
	}
}
inline void init(){
	memset(f,0x3f,sizeof(f));
	memset(ans,0x3f,sizeof(ans));
	ans[0] = 0;
	int sum = 0;
	for(int i = 1;i <= n;i++)
		if(!vis[i]){
			dfs(i);
			for(int j = sum;j >= 0;j--)
				for(int k = 0;k <= siz[i];k++)
					chk(ans[j + k],ans[j] + min(min(f[i][k][0][0],f[i][k][0][1]),min(f[i][k][1][0],f[i][k][1][1])));
			sum += siz[i];
		}
	for(int i = n - 1;i >= 0;i--)ans[i] = min(ans[i],ans[i + 1]);
}
inline void solve(){
	int s = read();
	int l = 0,r = n,ans = 0;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(::ans[mid] <= s)ans = mid,l = mid + 1;
		else r = mid - 1;
	}
	printf("%d\n",ans);
}
int main(){
	n = read(),m = read();
	for(int i = 1;i <= n;i++)val[i] = read();
	for(int u,v,i = 1;i <= m;i++)
		u = read(),v = read(),addedge(u,v),addedge(v,u);
	init();
	int q = read();
	while(q--)solve();
	return 0;
}

Compilation message

dzumbus.cpp: In function 'void dfs(int)':
dzumbus.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 0;i < G[u].size();i++){
      |                ~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 19456 KB Output is correct
2 Correct 27 ms 19456 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 19456 KB Output is correct
2 Correct 27 ms 19456 KB Output is correct
3 Correct 68 ms 21752 KB Output is correct
4 Correct 77 ms 22264 KB Output is correct
5 Correct 64 ms 21856 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 21368 KB Output is correct
2 Correct 50 ms 21112 KB Output is correct
3 Correct 59 ms 21624 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 19456 KB Output is correct
2 Correct 27 ms 19456 KB Output is correct
3 Correct 68 ms 21752 KB Output is correct
4 Correct 77 ms 22264 KB Output is correct
5 Correct 64 ms 21856 KB Output is correct
6 Correct 52 ms 21368 KB Output is correct
7 Correct 50 ms 21112 KB Output is correct
8 Correct 59 ms 21624 KB Output is correct
9 Correct 55 ms 21368 KB Output is correct
10 Correct 62 ms 22008 KB Output is correct
11 Correct 62 ms 21756 KB Output is correct