oj.uz

Submission #491518

# Submission time Handle Problem Language Result Execution time Memory
491518 2021-12-02T20:18:55 Z Nimbostratus Džumbus (COCI19_dzumbus) C++17
110 / 110
 52 ms 18632 KB 
#include "bits/stdc++.h"
#define endl '\n'
#define fi first
#define se second
#define int long long
using namespace std;
using lint = int;
using pii = pair<int, int>;
constexpr int maxn = 1005;
constexpr int maxq = 2e5 + 5;
constexpr int inf = 1e13;
constexpr int mod = 1e9 + 7;

int n, m, q;
vector<int> adj[maxn];
int d[maxn];
int dp[maxn][maxn][3];
int sz[maxn];
int now[maxn][3], prv[maxn][3];
int tin[maxn];
int timer;
int ans[maxq];
vector<pii> vec;

void dfs(int u) {
	for(int v : adj[u])
		if(tin[v] > tin[u])
			dfs(v);
	for(int k = 1; k <= sz[u]; k++)
		for(int j = 0; j <= 2; j++)
			now[k][j] = inf;
	now[0][0] = 0;
	now[0][1] = d[u];
	now[0][2] = inf;
	int psz = 1;
	for(int v : adj[u]) {
		if(tin[v] < tin[u])
			continue;
		for(int k = 0; k <= sz[u]; k++)
			for(int j = 0; j <= 2; j++) {
				prv[k][j] = now[k][j];
				now[k][j] = inf;
			}
		for(int a = 0; a <= sz[v]; a++)
			for(int b = 0; b <= psz; b++) {
				int r0 = min({dp[v][a][0], dp[v][a][1], dp[v][a][2]}) + prv[b][0];
				int r1 = dp[v][a][0] + prv[b][1];
				int r2 = min({
					dp[v][a][0] + prv[b][2],
					dp[v][a][2] + prv[b][2],
					a >= 1 ? dp[v][a - 1][1] + prv[b][2] : inf,
					b >= 1 ? dp[v][a][2] + prv[b - 1][1] : inf,
					a >= 1 && b >= 1 ? dp[v][a - 1][1] + prv[b - 1][1] : inf
				});
				now[a + b][0] = min(now[a + b][0], r0);
				now[a + b][1] = min(now[a + b][1], r1);
				now[a + b][2] = min(now[a + b][2], r2);
			}
		psz += sz[v];
	}
	for(int k = 0; k <= sz[u]; k++)
		for(int j = 0; j <= 2; j++)
			dp[u][k][j] = now[k][j];
}

void dfs2(int u) {
	tin[u] = ++timer;
	sz[u] = 1;
	for(int v : adj[u])
		if(!tin[v]) {
			dfs2(v);
			sz[u] += sz[v];
		}
}

void precomp() {
	d[0] = inf;
	sz[0] = 1;
	for(int i = 1; i <= n; i++)
		if(!tin[i]) {
			dfs2(i);
			adj[0].push_back(i);
			sz[0] += sz[i];
		}
	dfs(0);
}

signed main() {
	#ifdef Local
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> d[i];
	for(int i = 0, x, y; i < m; i++) {
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	precomp();
	cin >> q;
	for(int i = 1, x; i <= q; i++) {
		cin >> x;
		vec.push_back({x, i});
	}
	sort(vec.begin(), vec.end());
	for(int k = n; k >= 0; k--)
		while(!vec.empty() && vec.back().fi >= dp[0][k][0]) {
			ans[vec.back().se] = k;
			vec.pop_back();
		}
	for(int i = 1; i <= q; i++)
		cout << ans[i] << endl;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11084 KB Output is correct
2 Correct 12 ms 12232 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11084 KB Output is correct
2 Correct 12 ms 12232 KB Output is correct
3 Correct 45 ms 18632 KB Output is correct
4 Correct 52 ms 18592 KB Output is correct
5 Correct 48 ms 17732 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6448 KB Output is correct
2 Correct 40 ms 7428 KB Output is correct
3 Correct 36 ms 7864 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11084 KB Output is correct
2 Correct 12 ms 12232 KB Output is correct
3 Correct 45 ms 18632 KB Output is correct
4 Correct 52 ms 18592 KB Output is correct
5 Correct 48 ms 17732 KB Output is correct
6 Correct 32 ms 6448 KB Output is correct
7 Correct 40 ms 7428 KB Output is correct
8 Correct 36 ms 7864 KB Output is correct
9 Correct 39 ms 11820 KB Output is correct
10 Correct 43 ms 12200 KB Output is correct
11 Correct 43 ms 11828 KB Output is correct