This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
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);
}
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;
ans = min(ans, (d - mx) * j);
}
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |