#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[lim];
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;
}
bool ddfs(int node){
if(!node)return 1;
for(int j=initial[node];j<size(v[node])&&v[node][j]<=r;j++){
int to=v[node][j];
if(to==match[node])continue;
int toto=match[to];
if(level[toto]==-1&&(level[toto]=level[node]+1)&&ddfs(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);
v[a+m].pb(b);
}
for(int i=0;i<=m;i++){
sort(v[i].begin(),v[i].end());
}
int ans=0;
l=m+1,r=2*m;
while(cnt!=m&&r<=n+m){
while(1){
queue<int>q;
for(int i=0;i<=m;i++){
level[i]=-1;
p[i]=0;
if(!match[i]&&i){
level[i]=0;
q.push(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;
}
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]++;
}
}
l++;
for(;l<n+m;l++){
if(cnt!=m){
int lostone=0;
for(int i=0;i<=m;i++){
level[i]=-1;
if(i&&!match[i]){
lostone=i;
level[i]=0;
}
}
int val=ddfs(lostone);
if(val){
cnt++;
}else{
while(cnt!=m&&r<n+m){
r++;
bool found=0;
for(int j:v[r]){
if(level[j]!=-1){
found=1;
break;
}
}
if(found){
cnt++;
for(int i=0;i<=m;i++){
level[i]=-1;
if(i&&!match[i]){
lostone=i;
level[i]=0;
}
}
ddfs(lostone);
}
}
}
}
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 'bool ddfs(int64_t)':
marriage.cpp:40:30: 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]
40 | for(int j=initial[node];j<size(v[node])&&v[node][j]<=r;j++){
| ~^~~~~~~~~~~~~~
marriage.cpp: In function 'int main()':
marriage.cpp:85:43: 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]
85 | for(int pp=initial[now];pp<size(v[now])&&v[now][pp]<=r;pp++){
| ~~^~~~~~~~~~~~~
marriage.cpp:97:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
97 | if(val=dfs(i)){
| ~~~^~~~~~~
marriage.cpp:113:22: 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]
113 | if(initial[i]!=size(v[i])&&v[i][initial[i]]==l){
| ~~~~~~~~~~^~~~~~~~~~~~
marriage.cpp:164: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]
164 | if(initial[i]!=size(v[i])&&v[i][initial[i]]==l){
| ~~~~~~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1368 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1368 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1368 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1372 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 7 |
Runtime error |
307 ms |
262144 KB |
Execution killed with signal 9 |
| 8 |
Correct |
1 ms |
1624 KB |
Output is correct |
| 9 |
Execution timed out |
1582 ms |
1372 KB |
Time limit exceeded |
| 10 |
Correct |
1 ms |
1368 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
1372 KB |
Output isn't correct |
| 14 |
Runtime error |
361 ms |
262144 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
952 ms |
262144 KB |
Execution killed with signal 9 |
| 16 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 17 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 19 |
Correct |
1 ms |
1500 KB |
Output is correct |
| 20 |
Runtime error |
317 ms |
262144 KB |
Execution killed with signal 9 |
| 21 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 22 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 23 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 24 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 25 |
Runtime error |
239 ms |
262144 KB |
Execution killed with signal 9 |
| 26 |
Runtime error |
338 ms |
262144 KB |
Execution killed with signal 9 |
| 27 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 28 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 29 |
Correct |
2 ms |
1628 KB |
Output is correct |
| 30 |
Correct |
2 ms |
1628 KB |
Output is correct |
| 31 |
Runtime error |
246 ms |
262144 KB |
Execution killed with signal 9 |
| 32 |
Runtime error |
462 ms |
262144 KB |
Execution killed with signal 9 |
| 33 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 34 |
Correct |
4 ms |
1372 KB |
Output is correct |
| 35 |
Correct |
57 ms |
4932 KB |
Output is correct |
| 36 |
Correct |
38 ms |
4444 KB |
Output is correct |
| 37 |
Runtime error |
292 ms |
262144 KB |
Execution killed with signal 9 |
| 38 |
Correct |
17 ms |
5244 KB |
Output is correct |
| 39 |
Correct |
108 ms |
1620 KB |
Output is correct |
| 40 |
Correct |
44 ms |
1884 KB |
Output is correct |
| 41 |
Execution timed out |
1536 ms |
2808 KB |
Time limit exceeded |
| 42 |
Correct |
76 ms |
2484 KB |
Output is correct |
| 43 |
Correct |
52 ms |
3152 KB |
Output is correct |
| 44 |
Correct |
123 ms |
4500 KB |
Output is correct |
| 45 |
Correct |
121 ms |
2868 KB |
Output is correct |
| 46 |
Runtime error |
1126 ms |
262144 KB |
Execution killed with signal 9 |
| 47 |
Correct |
220 ms |
4948 KB |
Output is correct |
| 48 |
Correct |
205 ms |
4744 KB |
Output is correct |
| 49 |
Runtime error |
1033 ms |
262144 KB |
Execution killed with signal 9 |
| 50 |
Correct |
247 ms |
1728 KB |
Output is correct |
