Submission #711313

#TimeUsernameProblemLanguageResultExecution timeMemory
711313LeMurMarriage questions (IZhO14_marriage)C++14
86 / 100
423 ms4308 KiB
/////////////////////////////// _LeMur_ #define _CRT_SECURE_NO_WARNINGS #include <unordered_map> #include <unordered_set> #include <algorithm> #include <iostream> #include <cstring> #include <cassert> #include <chrono> #include <random> #include <bitset> #include <cstdio> #include <vector> #include <string> #include <stack> #include <tuple> #include <queue> #include <ctime> #include <cmath> #include <list> #include <map> #include <set> using namespace std; const int N = 50005; const int inf = 1000 * 1000 * 1000; const int mod = 998244353; // mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count()); mt19937 myrand(1337); int n, m, k; vector <int> g[N]; bool used[N]; int mt[N]; bool kuhn(int v, int L, int R) { if (used[v]) return false; used[v] = true; for (int i = 0; i < (int)g[v].size(); i++) { int to = g[v][i]; if (to < L) continue; if (to > R) break; if (mt[to] == -1 || kuhn(mt[to], L, R)) { mt[to] = v; return true; } } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> k; for (int i = 1; i <= k; i++) { int a, b; cin >> a >> b; a += m; g[a].push_back(b); g[b].push_back(a); } for (int i = 1; i <= m; i++) { sort(g[i].begin(), g[i].end()); } int ina = m, inb = n, ind = -1; while (ina <= inb) { int mid = (ina + inb) / 2; for (int i = 1; i <= mid; i++) { mt[i + m] = -1; } int cnt = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { used[j] = false; } bool flag = kuhn(i, 1, mid + m); if (flag) ++cnt; } if (cnt == m) { ind = mid; inb = mid - 1; } else { ina = mid + 1; } } if (ind == -1) { cout << 0 << endl; return 0; } for (int i = 1; i <= n; i++) { mt[i + m] = -1; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { used[j] = false; } kuhn(i, 1, ind + m); } int answ = n - ind + 1; for (int i = 1; i <= n; i++) { if (mt[i + m] == -1) { answ += n - ind + 1; continue; } int girl = mt[i + m]; while (ind <= n) { for (int j = 1; j <= m; j++) { used[j] = false; } bool flag = kuhn(girl, i + 1, ind + m); if (flag) break; ++ind; } if (ind == n + 1) break; answ += n - ind + 1; } cout << answ << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...