Submission #943692

#	Time	Username	Problem	Language	Result	Execution time	Memory
943692		iliaaaaa	Garden (JOI23_garden)	C++17	75 / 100	3061 ms	103508 KiB

garden

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define All(x) (x).begin(), (x).end()
#define len(x) (int) (x).size()
#define pb push_back

const int N = 5e5 + 7, D = 5000 + 7;
int n, m, d, mx, cnt[D], cnt2[D][D], hlp[D];
short par[D], mm[D];
vector<pii> vec[D];

int get_par(int u) {
	return par[u] < 0? u: par[u] = get_par(par[u]);
}

void merge(int u, int v) {
	u = get_par(u), v = get_par(v);
	if (u == v)
		return;
	if (par[u] < par[v])
		swap(u, v);
	par[v] += par[u];
	par[u] = v;
	mx = max(mx, -par[v]);
}

int32_t main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> d;
	memset(par, -1, sizeof par);
	vector<int> must;
	for (int i = 0; i < n; i++) {
		int p, q;
		cin >> p >> q;
		hlp[q]++;
		must.pb(p);
		mm[p] = true;
	}
	sort(All(must));
	must.resize(unique(All(must)) - must.begin());
	for (int i = 0; i < m; i++) {
		int r, s;
		cin >> r >> s;
		//vec[r].pb(s);
		cnt[s]++;
		cnt2[r][s]++;
	}
	for (int i = 0; i < d; i++)
		for (int j = 0; j < d; j++)
			if (cnt2[i][j] >= 1) 
				vec[i].pb({j, cnt2[i][j]});
	int rm;
	int ans = D * D;
	for (int i = 0; i < d; i++) {
		for (int j = 0; j < d; j++) {
			par[j] = -1;
			hlp[j] += cnt[j];
		}
		rm = len(must);
		mx = 0;
		for (int x = 0; x < d; x++) 
			if (!hlp[x]) {
				mx = max(mx, 1);
				if (!hlp[(x + 1) % d])
					merge(x, (x + 1) % d);

				if (!hlp[(x - 1 + d) % d])
					merge(x, (x - 1 + d) % d);
			}
			
		//cout << i << '\n';
		for (int j = 1; j <= d; j++) {
			int mod = (i + j - 1) % d;
			rm -= mm[mod];
			for (auto [x, c]: vec[mod]) {
				hlp[x] -= c;
				if (!hlp[x]) {
					mx = max(mx, 1);
					if (!hlp[(x + 1) % d])
						merge(x, (x + 1) % d);
					if (!hlp[(x - 1 + d) % d])
						merge(x, (x - 1 + d) % d);
				}
			}
			if (rm)
				continue;
			//cout << i << ' ' << j << ' ' << d - mx << '\n';
			//cout << i << ' ' << j << ' ' << tmp << '\n';
			ans = min(ans, (d - mx) * j);
		}
	}
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 0 / 25