Submission #38588

#	Time	Username	Problem	Language	Result	Execution time	Memory
38588		alenam0161	Marriage questions (IZhO14_marriage)	C++14	56 / 100	1500 ms	4948 KiB

marriage

#include<bits/stdc++.h>

#define ad push_back

using namespace std;
const int N = 40007 , M = 3007;
vector <int> g[N],g1[M];
bool used1[N],used2[M];
int ma[M],na[N];
bool try_kuhn(int x)
{
    if (used1[x]) return false;
    used1[x]=true;
    int i;
    for (auto to:g[x])
    if (ma[to]==0 || try_kuhn(ma[to]))
    {
        ma[to]=x;
        na[x]=to;
        return true;
    }
    return false;
}
int l,r=0;
bool try_kuhn2(int x)
{
    if (used2[x]) return false;
    used2[x]=true;
    int i;
    for (auto to:g1[x])
    if (to>l && to<=r && na[to]==0 || try_kuhn(na[to]))
    {
        na[to]=x;
        ma[x]=to;
        return true;
    }
    return false;
}
int main()
{
    int i,n,m,k,x,y;
    scanf("%d%d%d",&n,&m,&k);
    for (i=1;i<=k;i++)
    {
        scanf("%d%d",&x,&y);
        g[x].ad(y);
        g1[y].ad(x);
    }
    long long ans=0;
    int how=0;
    for (l=1;l<=n-m+1;l++)
    {
        while (how!=m && r<n)
        {
            r++;
            memset(used1,0,sizeof used1);
            how+=try_kuhn(r);
        }
        if ( how == m ) ans += n - r + 1;
        if (na[l]==0) continue;
        memset(used2,0,sizeof( used2));
        int gag=na[l];
        ma[na[l]]=0;
        na[l]=0;
        how--;
        how+=try_kuhn2(x);
    }
    cout<<ans<<"\n";
    return 0;
}

Compilation message (stderr)

marriage.cpp: In function 'bool try_kuhn(int)':
marriage.cpp:14:9: warning: unused variable 'i' [-Wunused-variable]
     int i;
         ^
marriage.cpp: In function 'bool try_kuhn2(int)':
marriage.cpp:31:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (to>l && to<=r && na[to]==0 || try_kuhn(na[to]))
                       ^
marriage.cpp:29:9: warning: unused variable 'i' [-Wunused-variable]
     int i;
         ^
marriage.cpp: In function 'int main()':
marriage.cpp:62:13: warning: unused variable 'gag' [-Wunused-variable]
         int gag=na[l];
             ^
marriage.cpp:42: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:45:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
                            ^

• Subtask 1: 56 / 100