oj.uz

Submission #829820

# Submission time Handle Problem Language Result Execution time Memory
829820 2023-08-18T15:14:37 Z jamielim Džumbus (COCI19_dzumbus) C++14
110 / 110
 673 ms 34884 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n,m;
int d[1005];
vector<int> adj[1005];
ll dp[1005][1005][2][2];
// min amount of dzumbus needed to get y people sharing in x's subtree
// z is flag for whether x is drunk, w is flag for whether x has any drunk child

int dfs(int x,int p){
	int subtree=1;
	dp[x][0][0][0]=0;
	dp[x][0][0][1]=0;
	dp[x][0][1][0]=0;
	dp[x][0][1][1]=LLINF;
	for(int i:adj[x]){
		if(i==p)continue;
		int csub=dfs(i,x);
		subtree+=csub;
		ll tmp[n+5][2][2];
		for(int k=0;k<=n;k++)for(int a=0;a<2;a++)for(int b=0;b<2;b++)tmp[k][a][b]=dp[x][k][a][b];
		for(int j=subtree;j>=0;j--){
			for(int k=0;k<=min(csub,j);k++){
				dp[x][j][0][0]=min(dp[x][j][0][0],min(dp[i][k][0][0],dp[i][k][0][1])+tmp[j-k][0][0]);
				dp[x][j][0][1]=min(dp[x][j][0][1],min(min(dp[i][k][1][0],dp[i][k][1][1])+tmp[j-k][0][1], // prv 1, now 1
												  min(min(dp[i][k][0][0],dp[i][k][0][1])+tmp[j-k][0][1], // prv 1, now 0
													  min(dp[i][k][1][0],dp[i][k][1][1])+tmp[j-k][0][0]))); // prv 0, now 1
				dp[x][j][1][0]=min(dp[x][j][1][0],min(dp[i][k][0][0],dp[i][k][0][1])+tmp[j-k][1][0]);
				dp[x][j][1][1]=min(dp[x][j][1][1],min(min((j-k>=1?dp[i][k][1][0]+tmp[j-k-1][1][1]:LLINF),
															  dp[i][k][1][1]+tmp[j-k][1][1]), // prv 1, now 1
												  min(min(dp[i][k][0][0],dp[i][k][0][1])+tmp[j-k][1][1], // prv 1, now 0
												      min((j-k>=2?dp[i][k][1][0]+tmp[j-k-2][1][0]:LLINF),
												          (j-k>=1?dp[i][k][1][1]+tmp[j-k-1][1][0]:LLINF))))); // prv 0, now 1. but need to -1 or -2
			}
		}
	}
	for(int i=0;i<=subtree;i++){
		dp[x][i][1][0]+=d[x];
		dp[x][i][1][1]+=d[x];
		if(dp[x][i][1][0]>LLINF)dp[x][i][1][0]=LLINF;
		if(dp[x][i][1][1]>LLINF)dp[x][i][1][1]=LLINF;
	}
	return subtree;
}

bool vis[1005];
void flood(int x){
	for(int i:adj[x]){
		if(!vis[i]){
			vis[i]=1;
			flood(i);
		}
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&d[i]);
	int a,b;
	for(int i=0;i<m;i++){
		scanf("%d%d",&a,&b);
		adj[a].pb(b);
		adj[b].pb(a);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			adj[0].pb(i);
			adj[i].pb(0);
			vis[i]=1;
			flood(i);
		}
	}
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<2;k++)for(int a=0;a<2;a++)dp[i][j][k][a]=LLINF;
	dfs(0,-1);
	int q;
	scanf("%d",&q);
	while(q--){
		scanf("%d",&a);
		for(int i=n;i>=0;i--){
			if(min(dp[0][i][0][0],dp[0][i][0][1])<=a){
				printf("%d\n",i);
				break;
			}
		}
	}
}

Compilation message

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
dzumbus.cpp:75:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  for(int i=1;i<=n;i++)scanf("%d",&d[i]);
      |                       ~~~~~^~~~~~~~~~~~
dzumbus.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~
dzumbus.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
dzumbus.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%d",&a);
      |   ~~~~~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 32032 KB Output is correct
2 Correct 513 ms 31956 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 32032 KB Output is correct
2 Correct 513 ms 31956 KB Output is correct
3 Correct 673 ms 34156 KB Output is correct
4 Correct 402 ms 34884 KB Output is correct
5 Correct 479 ms 34360 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3056 KB Output is correct
2 Correct 37 ms 2832 KB Output is correct
3 Correct 53 ms 3264 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 32032 KB Output is correct
2 Correct 513 ms 31956 KB Output is correct
3 Correct 673 ms 34156 KB Output is correct
4 Correct 402 ms 34884 KB Output is correct
5 Correct 479 ms 34360 KB Output is correct
6 Correct 34 ms 3056 KB Output is correct
7 Correct 37 ms 2832 KB Output is correct
8 Correct 53 ms 3264 KB Output is correct
9 Correct 84 ms 33924 KB Output is correct
10 Correct 92 ms 34576 KB Output is correct
11 Correct 201 ms 34364 KB Output is correct