Submission #38501

#	Time	Username	Problem	Language	Result	Execution time	Memory
38501		alenam0161	Marriage questions (IZhO14_marriage)	C++14	36 / 100	1500 ms	3124 KiB

marriage

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3+7;
vector<int> g[N],g1[N];
int n,m,k;
bool used[N];
int ma[N];
bool try_khun(int v){
    if(used[v]==true)return false;
    used[v]=true;
    for(auto to:g[v]){
        if(ma[to]==-1||try_khun(ma[to])){
            ma[to]=v;
            return true;
        }
    }
    return false;
}
/*
 how=0;
            memset(ma,-1,sizeof(ma));
            for(int j=l;j<=r;++j){
                memset(used,0,sizeof(used));
                how+=try_khun(j);
            }
            if(how==m)ans++;
                */
int main(){
    memset(ma,-1,sizeof(ma));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;++i){
        int u,v;
        scanf("%d%d",&v,&u);
        g[v].push_back(u);
        g1[u].push_back(v);
    }
    int how=0;
    long long ans=0;
    int l=1;
    for(int i=1;i<=n;++i){
        if(try_khun(i))how++;
        while(how==m){
            l++;
            if(l>n-m+2){
                  //  cout<<l<<" "<<n<<" "<<m<<" "<<i<<endl;
                cout<<ans<<endl;return 0;
            }
            how=0;
            memset(ma,-1,sizeof(ma));
            for(int j=l;j<=i;++j){
                memset(used,0,sizeof(used));
                how+=try_khun(j);
            }
        }
        ans+=l-1;
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:32: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:35:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&v,&u);
                            ^

• Subtask 1: 36 / 100