Submission #341233

#	Time	Username	Problem	Language	Result	Execution time	Memory
341233		juggernaut	Marriage questions (IZhO14_marriage)	C++14	44 / 100	33 ms	3948 KiB

marriage

#include<bits/stdc++.h>
using namespace std;
vector<int>g[100005];
int mt[100005];
int n,m,q;
bool used[100001];
int X,Y;
int ans=0;
clock_t start;
bool kuhn(int v){
    if(clock()-start>3000){
        cout<<ans;
        exit(0);
    }
    if(used[v]||v<X||v>Y)return false;
    used[v]=true;
    for(int to:g[v]){
        if(mt[to]==0||kuhn(mt[to])){
            mt[to]=v;
            return true;
        }
    }
    return false;
}
bool check(int l,int r){
    X=l,Y=r;
    for(int i=1;i<=n;i++)mt[i]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)used[j]=false;
        kuhn(i);
    }
    int c=0;
    for(int i=1;i<=n;i++)if(mt[i])c++;
    return c==m;
}
int main(){
    start=clock();
    scanf("%d%d%d",&n,&m,&q);
    if(n<m||q<m)return puts("0"),0;
    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
    }
    for(int GL=1;GL<=n;GL++){
        int l=GL,r=n+1;
        while(l<r){
            int mid=(l+r)>>1;
            if(check(GL,mid))r=mid;
            else l=mid+1;
        }
        ans+=n-l+1;
    }
    cout<<ans;
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     scanf("%d%d%d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
marriage.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 44 / 100