#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e4;
const int MAX_M = 2000;
vector<int> adj[MAX_M + 1];
bool vis[MAX_N + 1];
int pairB[MAX_N + 1];
set<int> unpaired;
int L, R;
bool pairup(int u) {
if (u == 0)
return true;
if (vis[u])
return false;
vis[u] = true;
for (int v: adj[u]) {
if (v < L || v > R)
continue;
if (pairup(pairB[v])) {
pairB[v] = u;
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < k; i++) {
int a, b;
cin >> b >> a;
adj[a].push_back(b);
}
for (int i = 1; i <= m; i++)
unpaired.insert(i);
int l = 1;
long long ans = 0;
for (int r = 1; r <= n; r++) {
L = l;
R = r;
vector<int> ers;
for (int i = 1; i <= m; i++)
vis[i] = false;
for (int i: unpaired) {
if (pairup(i))
ers.push_back(i);
}
for (int i: ers)
unpaired.erase(i);
if (unpaired.empty()) {
while (l <= r && unpaired.empty()) {
int i = pairB[l];
pairB[l] = 0;
l++;
L = l, R = r;
unpaired.insert(i);
for (int j = 1; j <= m; j++)
vis[j] = false;
if (pairup(i))
unpaired.erase(i);
}
l--;
ans += l;
// printf("%d %d\n", l, r);
}
}
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |