Submission #1026076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026076		vjudge1	Marriage questions (IZhO14_marriage)	C++17	36 / 100	1592 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[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 (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 '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){
      |                ~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 36 / 100