# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
338781 | Tosic | Marriage questions (IZhO14_marriage) | C++14 | 28 ms | 1004 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>
#define maxn 100010
using namespace std;
long long ans;
int n,m, k, fMatch[maxn], iterNum[maxn], itV;
vector<vector<int> > gr;
bool dfs(int x, int& l, int& r){
if(iterNum[x] == itV){
return 0;
}
iterNum[x] = itV;
for(auto i : gr[x]){
if(i>=l and i <= r and (!fMatch[x] or dfs(fMatch[i], l, r)) ){
fMatch[i] = x;
return 1;
}
}
return 0;
}
int main(){
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
cin >> n >> m >> k;
gr.resize(m+1, vector<int>());
for(int i = 0; i < k; ++i){
int a, b;
cin >> a >> b;
gr[b].push_back(a);
//gr[b].push_back(a);
}
int j = 1;
vector<int> notF;
for(int i = 1; i <= m; ++i){
notF.push_back(i);
}
for(int i = 1; i <= n; ++i){
while(j <= n){
if(!notF.size()){
break;
}
for(int j0 = notF.size()-1; j0 >= 0; --j0){
++itV;if(dfs(notF[j0], i, j)){
notF.pop_back();
} else {
break;
}
}
if(!notF.size()){
break;
}
++j;
//cerr << j << '\n';
}
if(notF.size()){
break;
}
//cerr << j << '\n';
ans += n-j;
if(fMatch[i]){
notF.push_back(fMatch[i]);
fMatch[i] = 0;
}
}
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |