oj.uz

Submission #338165

# Submission time Handle Problem Language Result Execution time Memory
338165 2020-12-22T15:26:58 Z minoum Džumbus (COCI19_dzumbus) C++17
50 / 110
 78 ms 43116 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 1000+10;
const ll inf = 1e17;
int n, m;
ll dp[MAXN][MAXN][3], s[MAXN][MAXN], d[MAXN], sz[MAXN], d2[MAXN][3], mn[MAXN][MAXN];
vector <int> adj[MAXN], rs;
bool mark[MAXN];

void dfs(int v){
	mark[v] = true; sz[v] = 1;
	dp[v][0][0] = 0ll; dp[v][0][1] = d[v]; mn[v][0] = 0ll;
	for(int u: adj[v]){
		if(mark[u]) continue;
		dfs(u);
		for(int i = 0; i <= sz[u]+sz[v]; i++){
			/*d2[i][0] = dp[v][i][0];
			d2[i][1] = dp[v][i][1];
			d2[i][2] = dp[v][i][2];
			*/
			d2[i][0] = inf;
			d2[i][1] = inf;
			d2[i][2] = inf;
		}
		for(int i = 0; i <= sz[v]; i++)
			for(int j = i; j <= sz[u]+sz[v]; j++){
				d2[j][0] = min(d2[j][0], dp[v][i][0]+mn[u][j-i]);
				d2[j][1] = min(d2[j][1], dp[v][i][1]+dp[u][j-i][0]);
				d2[j][2] = min(d2[j][2], dp[v][i][2]+min(dp[u][j-i][0], dp[u][j-i][2]));
				if(j-i-1>=0) d2[j][2] = min(d2[j][2], dp[v][i][1]+dp[u][j-i-1][2]);
				if(j-i-2>=0) d2[j][2] = min(d2[j][2], dp[v][i][1]+dp[u][j-i-2][1]);
				if(j-i-1>=0) d2[j][2] = min(d2[j][2], dp[v][i][2]+dp[u][j-i-1][1]);
			}
		for(int i = 0; i <= sz[u]+sz[v]; i++){
			dp[v][i][0] = min(inf, d2[i][0]);
			dp[v][i][1] = min(inf, d2[i][1]);
			dp[v][i][2] = min(inf, d2[i][2]);
		}
		sz[v] += sz[u];
	}
	for(int i = 0; i <= sz[v]; i++)
		mn[v][i] = min(dp[v][i][0], min(dp[v][i][1], dp[v][i][2]));
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> d[i];
		for(int j = 0; j <= n; j++) dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = s[i][j] = mn[i][j] = inf; 
	} 
	for(int i = 0; i < m; i++){
		int u, v;
		cin	>> u >> v; u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i = 0; i < n; i++)
		if(!mark[i]){
			dfs(i);
			rs.push_back(i);
		}
	for(int i = 0; i <= n; i++)
		for(int j = 1; j <= n; j++) s[i][j] = inf;
	s[0][0] = 0ll;
	int cnt = 0;
	for(int i = 0; i < (int)rs.size(); i++){
		int v = rs[i];
		cnt += sz[v];
		s[i+1][0] = 0ll;
		for(int j = 1; j <= cnt; j++)
			for(int k = 0; k <= min((int)sz[v], j); k++){
				s[i+1][j] = min(s[i+1][j], mn[v][k]+s[i][j-k]);
			}
	}	
	vector <pair<ll, int>> ans;
	cnt = (int)rs.size();
	for(int i = 0; i <= n; i++)
		if(s[1][i] != inf) ans.push_back({s[1][i], i});
	sort(ans.begin(), ans.end());
	for(int i = 1; i < (int)ans.size(); i++) ans[i].second = max(ans[i].second, ans[i-1].second);
	int q;
	cin >> q;
	while(q--){
		ll s1;
		cin >> s1;
		pair<ll, int> p = {s1, INT_MAX};
		int ind = upper_bound(ans.begin(), ans.end(), p) - ans.begin() - 1;
		cout << ans[ind].second << '\n';
	}
	return 0; 
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 40172 KB Output is correct
2 Correct 32 ms 40172 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 40172 KB Output is correct
2 Correct 32 ms 40172 KB Output is correct
3 Correct 74 ms 42280 KB Output is correct
4 Correct 78 ms 43116 KB Output is correct
5 Correct 77 ms 42476 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 4076 KB Output is correct
2 Incorrect 40 ms 3692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 40172 KB Output is correct
2 Correct 32 ms 40172 KB Output is correct
3 Correct 74 ms 42280 KB Output is correct
4 Correct 78 ms 43116 KB Output is correct
5 Correct 77 ms 42476 KB Output is correct
6 Correct 43 ms 4076 KB Output is correct
7 Incorrect 40 ms 3692 KB Output isn't correct
8 Halted 0 ms 0 KB -