| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 905023 | khachatur25 | Marriage questions (IZhO14_marriage) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Online C++ compiler to run C++ program online#include <bits/stdc++.h>using namespace std;const int N = 32005;int n,m,k;vector<int>g[N];int a,b;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 < 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(nullptr); cin.tie(NULL); cin >> n >> m >> k; for(int i = 1;i <= k;i++){ scanf("%d""%d",&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, idx = -1; while(ina <= inb){ int mid = (ina + inb) >> 1; 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 f = kuhn(i,1,mid + m); if(f)cnt++; } if(cnt == m){ idx = mid; inb = mid - 1; } else{ ina = mid - 1; } } if(idx = -1){ cout << 0; 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,idx + m); } int ans = n - idx + 1; for(int i = 1;i <= n;i++){ if(mt[i + m] == -1){ ans += n - idx + 1; continue; } int girl = mt[i + m]; while(idx <= n){ for(int j = 1;j <= m;j++){ used[j] = false; } bool f = kuhn(girl,i + 1 + m,idx + m); if(f)break; idx++; } if(idx == n + 1)break; ans += n - idx + 1; } cout << ans;}