Submission #1026090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026090		vjudge1	Marriage questions (IZhO14_marriage)	C++17	72 / 100	1582 ms	262144 KiB

marriage

#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 (stderr)

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){
      |                ~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 72 / 100