oj.uz

Submission #448819

# Submission time Handle Problem Language Result Execution time Memory
448819 2021-08-01T20:27:58 Z Antekb Džumbus (COCI19_dzumbus) C++14
110 / 110
 473 ms 7132 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
const long long inf=1e18;
vector<long long> dp[2][N];//0-opt, 1-zawiera v
int siz[N], vis[N];
long long val[N];
vector<int> E[N];
void init(int v){
	vis[v]=1;
	for(int u:E[v]){
		if(!vis[u]){
			init(u);
		}
	}
}
void dfs(int v){
	siz[v]=1;
	dp[0][v]={0, inf};
	dp[1][v]={inf, inf};
	for(int u:E[v]){
		if(!siz[u]){
			dfs(u);
			siz[v]+=siz[u];
			vector<long long> V(siz[v]+1, inf), V2(siz[v]+1, inf);
			V[0]=0;
			for(int i=0; i<siz[v]-siz[u]; i++){
				for(int j=0; j<=siz[u]; j++){
					V[i+j]=min(V[i+j], dp[0][v][i]+min(dp[0][u][j], dp[1][u][j]));
				}
			}
			for(int i=0; i<=siz[v]-siz[u]; i++){
				for(int j=0; j<=siz[u]; j++){
					V2[i+j]=min(V2[i+j], dp[1][v][i]+min(dp[0][u][j], dp[1][u][j]));
				}
			}
			for(int i=0; i<siz[v]-siz[u]; i++){
				for(int j=0; j<=siz[u]; j++){
					V2[i+j+1]=min(V2[i+j+1], dp[0][v][i]+dp[1][u][j]+val[v]);
				}
			}
			for(int i=0; i<=siz[v]-siz[u]; i++){
				for(int j=0; j<siz[u]; j++){
					V2[i+j+1]=min(V2[i+j+1], dp[1][v][i]+dp[0][u][j]+val[u]);
				}
			}
			for(int i=0; i<siz[v]-siz[u]; i++){
				for(int j=0; j<siz[u]; j++){
					V2[i+j+2]=min(V2[i+j+2], dp[0][v][i]+dp[0][u][j]+val[v]+val[u]);
				}
			}
			for(int i=0; i<=siz[v]-siz[u]; i++){
				V[i]=min(V[i], dp[0][v][i]);
				V2[i]=min(V2[i], dp[1][v][i]);
			}
			dp[0][v]=V;
			dp[1][v]=V2;
		}
	}
	/*for(int i=siz[v]; i>=0; i--){
		dp[0][v][i]=min(dp[0][v][i], dp[1][v][i]);
		if(i!=siz[v]){
			dp[0][v][i]=min(dp[0][v][i], dp[0][v][i+1]);
		}
	}*/
}
int main(){
	int n, m;
	cin>>n>>m;
	val[0]=inf;
	for(int i=1; i<=n; i++)cin>>val[i];
	for(int i=0; i<m; i++){
		int u, v;
		cin>>u>>v;
		E[u].push_back(v);
		E[v].push_back(u);
	}
	for(int i=1; i<=n; i++){
		if(!vis[i]){
			init(i);
			E[0].push_back(i);
		}
	}
	dfs(0);
	for(int i=siz[0]-1; i>=0; i--){
		dp[0][0][i]=min(dp[0][0][i], dp[0][0][i+1]);
	}
	//for(long long i:dp[0][0])cout<<i<<" ";cout<<"\n";
	int q;
	cin>>q;
	while(q--){
		int s;
		cin>>s;
		int t=upper_bound(dp[0][0].begin(), dp[0][0].end(), s)-dp[0][0].begin()-1;
		cout<<t<<"\n";
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5196 KB Output is correct
2 Correct 11 ms 6936 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5196 KB Output is correct
2 Correct 11 ms 6936 KB Output is correct
3 Correct 408 ms 7132 KB Output is correct
4 Correct 430 ms 6464 KB Output is correct
5 Correct 473 ms 5572 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 1200 KB Output is correct
2 Correct 397 ms 2236 KB Output is correct
3 Correct 448 ms 2748 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5196 KB Output is correct
2 Correct 11 ms 6936 KB Output is correct
3 Correct 408 ms 7132 KB Output is correct
4 Correct 430 ms 6464 KB Output is correct
5 Correct 473 ms 5572 KB Output is correct
6 Correct 398 ms 1200 KB Output is correct
7 Correct 397 ms 2236 KB Output is correct
8 Correct 448 ms 2748 KB Output is correct
9 Correct 402 ms 2844 KB Output is correct
10 Correct 425 ms 3268 KB Output is correct
11 Correct 430 ms 2976 KB Output is correct