# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
91515 | mirbek01 | Marriage questions (IZhO14_marriage) | C++11 | 271 ms | 4120 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.
# include <bits/stdc++.h>
using namespace std;
const int N = 33002;
int n, m, k, mt[N], cnt, used[N], ans, L, R, pt = 1;
vector <int> g[N], gr[N], mr;
bool dfs(int v){
if(used[v] == cnt)
return 0;
used[v] = cnt;
for(int i = (int)g[v].size() - 1; i >= 0; i --){
int to = g[v][i];
if(to < L) break;
if(mt[to] == -1 || dfs(mt[to])){
mt[to] = v;
mt[v] = to;
return true;
}
}
return false;
}
bool check(){
while(!mr.empty()){
int v = mr.back();
if(mt[v] == -1){
cnt ++;
if(!dfs(v))
return false;
}
mr.pop_back();
}
return mr.empty();
}
int main(){
scanf("%d %d %d", &n, &m, &k);
for(int i = 1; i <= k; i ++){
int a, b;
scanf("%d %d", &a, &b);
gr[a].push_back(b + n);
}
memset(mt, -1, sizeof(mt));
for(int i = n + 1; i <= n + m; i ++)
mr.push_back(i);
for(int j = 0; j < gr[1].size(); j ++){
int v = gr[1][j];
g[v].push_back(1);
}
for(int i = 1; i <= n; i ++){
L = i, R = pt;
while(pt <= n && !check()){
pt ++, R = pt;
for(int j = 0; j < gr[pt].size(); j ++){
int v = gr[pt][j];
g[v].push_back(pt);
}
}
ans += n - pt + 1;
if(mt[L] != -1){
mr.push_back(mt[L]);
mt[mt[L]] = -1;
}
}
printf("%d", ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |