Submission #1256415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256415		kerem	Džumbus (COCI19_dzumbus)	C++20	0 / 110	17 ms	24128 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][3];
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][2]=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;j<=sz[u];j++){
				dp[x][i+j][0]=min(dp[x][i+j][0],dp[x][i][0]+dp[u][j][0]);
				dp[x][i+j][0]=min(dp[x][i+j][0],dp[x][i][0]+dp[u][j][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]);
				dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][1]+dp[u][j][2]);
				dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][0]+dp[u][j][1]);
				dp[x][i+j][1]=min(dp[x][i+j][1],dp[x][i][0]+dp[u][j][2]);
				
				dp[x][i+j][2]=min(dp[x][i+j][2],dp[x][i][2]+dp[u][j][0]);
			}
		}
		sz[x]+=sz[u];
	}
	for(int i=sz[x];i>0;i--)
		dp[x][i][1]=min(dp[x][i][1],dp[x][i-1][1]+cost[x]);
}
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]=dp[i][j][2]=inf;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			g[0].pb(i);
			init(i,0);
		}
	}
	dfs(0,0);
	vector<pii> ans;
	for(int i=0;i<=n;i++){
		pii p={dp[0][i][0],i};
		while(!ans.empty() && ans.back().fr>=p.fr)
			ans.pop_back();
		ans.pb(p);
	}
	cin >> q;
	while(q--){
		int x;
		cin >> x;
		pii p={x,n};
		int t=upper_bound(all(ans),p)-ans.begin()-1;
		cout << ans[t].sc << "\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