Submission #38587

#	Time	Username	Problem	Language	Result	Execution time	Memory
38587		alenam0161	Marriage questions (IZhO14_marriage)	C++14	12 / 100	1489 ms	4504 KiB

marriage

#include <bits/stdc++.h>

#define ad push_back


using namespace std;

const int Mx = 30007 , Mn = 2007;

vector<int> g[Mx],g1[Mn];
bool used1[Mx],used2[Mn];
int m1[Mx],m2[Mn];
bool try_khun(int v){
    if(used1[v])return false;
    used1[v]=true;
    for(auto to:g[v]){
        if(m1[to]==0||try_khun(m1[to])){
            m1[to]=v;
            m2[v]=to;
            return true;
        }
    }
    return false;
}
bool try_khun2(int l,int r,int v){
   if(used2[v])return false;
   used2[v]=true;
   for(auto to:g1[v]){
       if((to>l&&to<=r)&&(m2[to]==0||try_khun2(l,r,to))){
        m2[to]=v;
        m1[v]=to;
        return true;
       }
   }

   return true;
}
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        g[v].ad(u);
        g1[u].ad(v);
    }
    long long ans=0;
    int r=0;
    int how=0;
    for(int i=1;i<=n;++i){
        while(how!=m&&r<n){
            r++;
            memset(used1,0,sizeof(used1));
            how+=try_khun(r);
        }
        if(how!=m&&r==n)break;
        if(how==m)ans+=n-r+1;
        cout<<i<<" "<<r<<endl;
        if(m2[i]==0)continue;
        int gag=m2[i];
        m1[m2[i]]=0;
        m2[i]=0;
        how--;
        memset(used2,0,sizeof(used2));
        ans+=try_khun2(i,r,gag);
    }
    cout<<ans<<"\n";
    return 0;
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:41:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&k);
                             ^
marriage.cpp:44:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&u,&v);
                            ^

• Subtask 1: 12 / 100