Submission #31474

#	Time	Username	Problem	Language	Result	Execution time	Memory
31474		hamlet	Marriage questions (IZhO14_marriage)	C++14	40 / 100	1500 ms	4636 KiB

marriage

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
vector <int> a[30010],b[2010];
bool used[30010],used2[2010];
int mt[2010],nt[30010];
bool try_kuhn(int x)
{
    if (used[x]) return false;
    used[x]=true;
    int i;
    for (i=0;i<a[x].size();i++)
    if (mt[a[x][i]]==0 || try_kuhn(mt[a[x][i]]))
    {
        mt[a[x][i]]=x;
        nt[x]=a[x][i];
        return true;
    }
    return false;
}
int l,r=0;
bool try_kuhn2(int x)
{
    if (used2[x]) return false;
    used2[x]=true;
    int i;
    for (i=0;i<b[x].size();i++)
    if (b[x][i]>l && b[x][i]<=r && nt[b[x][i]]==0 || try_kuhn(nt[b[x][i]]))
    {
        nt[b[x][i]]=x;
        mt[x]=b[x][i];
        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);
        a[x].push_back(y);
        b[y].push_back(x);
    }
    int ans=0,p=0;
    for (l=1;l<=n-m+1;l++)
    {
        while (p!=m && r<n)
        {
            r++;
            memset(used,0,sizeof used);
            p+=try_kuhn(r);
        }
        if (p==m) ans+=n-r+1;
        if (nt[l]==0) continue;
        memset(used2,0,sizeof used2);
        x=nt[l];
        mt[nt[l]]=0;
        nt[l]=0;
        p--;
        p+=try_kuhn2(x);
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

marriage.cpp: In function 'bool try_kuhn(int)':
marriage.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<a[x].size();i++)
               ^
marriage.cpp: In function 'bool try_kuhn2(int)':
marriage.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<b[x].size();i++)
               ^
marriage.cpp:30:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (b[x][i]>l && b[x][i]<=r && nt[b[x][i]]==0 || try_kuhn(nt[b[x][i]]))
                                 ^
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",&x,&y);
                            ^

• Subtask 1: 40 / 100