Submission #943664

#	Time	Username	Problem	Language	Result	Execution time	Memory
943664		iliaaaaa	Garden (JOI23_garden)	C++14	75 / 100	3052 ms	8168 KiB

garden

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
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], hlp[D], par[D];
vector<int> vec[D];

/*struct Node {
	int ans, pre, suf;
	bool all;
}seg[D << 2];

Node merge(Node &a, Node &b) {
	Node res;
	res.all = (a.all && b.all);
	res.pre = max(a.pre, a.all * (a.pre + b.pre));
	res.suf = max(b.suf, b.all * (b.suf + a.suf));
	res.ans = max({a.ans, b.ans, a.suf + b.pre});
	return res;
}*/

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);
	set<int> must;
	for (int i = 0; i < n; i++) {
		int p, q;
		cin >> p >> q;
		hlp[q]++;
		must.insert(p);
	}
	for (int i = 0; i < m; i++) {
		int r, s;
		cin >> r >> s;
		vec[r].pb(s);
		cnt[s]++;
	}
	set<int> rm;
	int ans = D * D;
	for (int i = 0; i < d; i++) {
		memset(par, -1, sizeof par);
		for (int j = 0; j < d; j++)
			hlp[j] += cnt[j];
		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);
			}
			
		rm = must;
		//cout << i << '\n';
		for (int j = 1; j <= d; j++) {
			int mod = (i + j - 1) % d;
			rm.erase(mod);
			for (int x: vec[mod]) {
				hlp[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);
				}
			}
			if (len(rm))
				continue;
			int tmp = d - mx;
			//cout << i << ' ' << j << ' ' << d - mx << '\n';
			//cout << i << ' ' << j << ' ' << tmp << '\n';
			ans = min(ans, tmp * 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