제출 #1245132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245132		PlayVoltz	Džumbus (COCI19_dzumbus)	C++20	110 / 110	283 ms	101588 KiB

dzumbus

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n;
vector <bool> visited;
vector<int> vect, subtree;
vector<vector<int> > graph;
vector<vector<vector<int> > > dp;

void check(int node){
	visited[node]=1;
	for (auto num:graph[node])if (!visited[num])check(num);
}

void dfs(int node, int par){
	visited[node]=1;
	vector<vector<int> > temp(n+5, vector<int>(3, LLONG_MAX/2));
	dp[node][0][0]=temp[0][0]=0;
	if(node)dp[node][0][1]=temp[0][1]=vect[node];
	for (auto num:graph[node])if (num!=par){
		dfs(num, node);
		for (int i=0; i<=subtree[node]; ++i)for (int j=0; j<=subtree[num]; ++j){
			temp[i+j][0]=min(temp[i+j][0], dp[node][i][0]+min({dp[num][j][0], dp[num][j][1], dp[num][j][2]}));
			temp[i+j][1]=min(temp[i+j][1], dp[node][i][1]+dp[num][j][0]);
			temp[i+j][2]=min(temp[i+j][2], dp[node][i][2]+min(dp[num][j][0], dp[num][j][2]));
			temp[i+j+1][2]=min(temp[i+j+1][2], dp[node][i][1]+dp[num][j][2]);
			temp[i+j+1][2]=min(temp[i+j+1][2], dp[node][i][2]+dp[num][j][1]);
			temp[i+j+2][2]=min(temp[i+j+2][2], dp[node][i][1]+dp[num][j][1]);
		}
		for (int i=0; i<=n; ++i)for (int j=0; j<3; ++j)dp[node][i][j]=temp[i][j];
		subtree[node]+=subtree[num];
	}
}

int32_t main(){
	int m, a, b;
	cin>>n>>m;
	graph.resize(n+1);
	vect.resize(n+1);
	visited.resize(n+1, 0);
	subtree.resize(n+1, 1);
	dp.resize(n+1, vector<vector<int> >(n+1, vector<int>(3, LLONG_MAX/2)));
	for (int i=1; i<=n; ++i)cin>>vect[i];
	while (m--){
		cin>>a>>b;
		graph[a].pb(b);
		graph[b].pb(a);
	}
	for (int i=1; i<=n; ++i)if (!visited[i])check(i), graph[0].pb(i);
	visited.assign(n+1, 0);
	dfs(0, 0);
	vector<int> ans(n, 0);
	for (int i=2; i<=n; ++i)ans[i-1]=dp[0][i][0];
	for (int i=n-2; i>=1; --i)ans[i]=min(ans[i], ans[i+1]);
	cin>>m;
	while (m--){
		cin>>a;
		int res=(upper_bound(ans.begin(), ans.end(), a)-ans.begin());
		if (res==1)res=0;
		cout<<res<<"\n";
	}
}

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