#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define pb push_back
const int llim=3000;
const int lim=40000;
int mod=1e9+7;
const int inf=INT_MAX;
using pii=pair<int,int>;
int cnt=0;
vector<int>v[llim];
int p[llim],initial[llim];
int match[lim],level[llim];
int l,r;
bool dfs(int node){
if(!node)return 1;
for(;p[node]<size(v[node])&&v[node][p[node]]<=r;p[node]++){
int to=v[node][p[node]];
if(to==match[node])continue;
int toto=match[to];
if(level[toto]==level[node]+1&&dfs(toto)){
match[to]=node;
match[node]=to;
return 1;
}
}
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local
freopen(".in","r",stdin);freopen(".out","w",stdout);
#endif
int n,m,k;
cin>>n>>m>>k;
for(int i=0;i<k;i++){
int a,b;
cin>>a>>b;
v[b].pb(a+m);
}
for(int i=0;i<=m;i++){
sort(v[i].begin(),v[i].end());
}
int ans=0;
for(l=m+1,r=2*m;l<n+m;l++){
while(cnt!=m&&r<=n+m){
while(1){
queue<int>q;
for(int i=0;i<=m;i++){
level[i]=-1;
if(!match[i]&&i){
level[i]=0;
q.push(i);
}
p[i]=initial[i];
}
while(q.size()){
int now=q.front();
q.pop();
for(int pp=initial[now];pp<size(v[now])&&v[now][pp]<=r;pp++){
int j=v[now][pp];
if(j!=match[now]){
level[match[j]]=level[now]+1;
q.push(match[j]);
}
}
}
if(level[0]==-1)break;
for(int i=1;i<=m;i++){
if(match[i])continue;
int val;
if(val=dfs(i)){
cnt+=val;
}
}
}
if(cnt!=m)r++;
}
if(cnt==m){
ans+=n+m-r+1;
}else break;
if(match[l]){
match[match[l]]=0;
match[l]=0;
cnt--;
}
for(int i=1;i<=m;i++){
if(initial[i]!=size(v[i])&&v[i][initial[i]]==l){
initial[i]++;
}
}
}
cout<<ans<<"\n";
}
Compilation message
marriage.cpp: In function 'bool dfs(int64_t)':
marriage.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(;p[node]<size(v[node])&&v[node][p[node]]<=r;p[node]++){
| ~~~~~~~^~~~~~~~~~~~~~
marriage.cpp: In function 'int main()':
marriage.cpp:69:47: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int pp=initial[now];pp<size(v[now])&&v[now][pp]<=r;pp++){
| ~~^~~~~~~~~~~~~
marriage.cpp:81:27: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
81 | if(val=dfs(i)){
| ~~~^~~~~~~
marriage.cpp:97:26: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | if(initial[i]!=size(v[i])&&v[i][initial[i]]==l){
| ~~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1543 ms |
348 KB |
Time limit exceeded |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Runtime error |
310 ms |
262144 KB |
Execution killed with signal 9 |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Execution timed out |
1592 ms |
348 KB |
Time limit exceeded |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 14 |
Runtime error |
322 ms |
262144 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
978 ms |
262144 KB |
Execution killed with signal 9 |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Runtime error |
387 ms |
262144 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
509 ms |
262144 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
209 ms |
262144 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
297 ms |
262144 KB |
Execution killed with signal 9 |
| 21 |
Correct |
0 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
348 KB |
Output is correct |
| 23 |
Runtime error |
252 ms |
262144 KB |
Execution killed with signal 9 |
| 24 |
Runtime error |
225 ms |
262144 KB |
Execution killed with signal 9 |
| 25 |
Runtime error |
226 ms |
262144 KB |
Execution killed with signal 9 |
| 26 |
Runtime error |
372 ms |
262144 KB |
Execution killed with signal 9 |
| 27 |
Correct |
1 ms |
348 KB |
Output is correct |
| 28 |
Correct |
1 ms |
348 KB |
Output is correct |
| 29 |
Runtime error |
222 ms |
262144 KB |
Execution killed with signal 9 |
| 30 |
Runtime error |
221 ms |
262144 KB |
Execution killed with signal 9 |
| 31 |
Runtime error |
238 ms |
262144 KB |
Execution killed with signal 9 |
| 32 |
Runtime error |
433 ms |
262144 KB |
Execution killed with signal 9 |
| 33 |
Correct |
2 ms |
348 KB |
Output is correct |
| 34 |
Correct |
6 ms |
604 KB |
Output is correct |
| 35 |
Runtime error |
209 ms |
262144 KB |
Execution killed with signal 9 |
| 36 |
Runtime error |
218 ms |
262144 KB |
Execution killed with signal 9 |
| 37 |
Runtime error |
298 ms |
262144 KB |
Execution killed with signal 9 |
| 38 |
Runtime error |
227 ms |
262144 KB |
Execution killed with signal 9 |
| 39 |
Correct |
141 ms |
604 KB |
Output is correct |
| 40 |
Correct |
42 ms |
888 KB |
Output is correct |
| 41 |
Execution timed out |
1544 ms |
1884 KB |
Time limit exceeded |
| 42 |
Runtime error |
443 ms |
262144 KB |
Execution killed with signal 9 |
| 43 |
Runtime error |
354 ms |
262144 KB |
Execution killed with signal 9 |
| 44 |
Runtime error |
329 ms |
262144 KB |
Execution killed with signal 9 |
| 45 |
Execution timed out |
1561 ms |
1372 KB |
Time limit exceeded |
| 46 |
Runtime error |
1065 ms |
262144 KB |
Execution killed with signal 9 |
| 47 |
Runtime error |
510 ms |
262144 KB |
Execution killed with signal 9 |
| 48 |
Runtime error |
473 ms |
262144 KB |
Execution killed with signal 9 |
| 49 |
Runtime error |
874 ms |
262144 KB |
Execution killed with signal 9 |
| 50 |
Correct |
349 ms |
604 KB |
Output is correct |
