Submission #1254902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254902		kerem	Džumbus (COCI19_dzumbus)	C++20	0 / 110	17 ms	16192 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e15
#define N 1000
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;

int n,m,q,cost[N+5],sz[N+5],vis[N+5],dp[N+5][N+5][2];
vector<int> g[N+5];

void init(int x,int ata){
	vis[x]=1;
	for(auto u:g[x])
		if(u!=ata) init(u,x);
}
void dfs(int x,int ata){
	sz[x]=1;
	dp[x][0][0]=0;
	dp[x][1][1]=cost[x];
	for(auto u:g[x]){
		if(u==ata) continue;
		dfs(u,x);
		for(int i=sz[x];i>=0;i--){
			for(int j=1;i+j<=n && j<=sz[u];j++){
				if(j!=1) dp[x][i+j][0]=min(dp[x][i+j][0],dp[x][i][0]+min(dp[u][j][0],dp[u][j][1]));
				if(i!=1) dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][1]+dp[u][j][0]);
				dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][1]+dp[u][j][1]);
			}
		}
		sz[x]+=sz[u];
	}
}
void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++)
		cin >> cost[i];
	for(int i=0;i<m;i++){
		int x,y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	for(int i=0;i<n+5;i++)
		for(int j=0;j<n+5;j++)
			dp[i][j][0]=dp[i][j][1]=inf;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			g[0].pb(i);
			init(i,0);
		}
	}
	dfs(0,0);
	vector<int> ans;
	for(int i=2;i<=n;i++)
		ans.pb(dp[0][i][0]);
	cin >> q;
	while(q--){
		int x;
		cin >> x;
		int t=upper_bound(all(ans),x)-ans.begin()-1;
		if(t<0) cout << 0 << "\n";
		else cout << t+2 << "\n";
	}
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30