Submission #341189

#	Time	Username	Problem	Language	Result	Execution time	Memory
341189		juggernaut	Marriage questions (IZhO14_marriage)	C++14	48 / 100	1600 ms	4588 KiB

marriage

//Just try and the idea will come!
#include<bits/stdc++.h>
#define int long long int
using namespace std;
int n,m,k,x,y,cnt,mt[100001];
vector<vector<int>>g(100001);
bool used[100001];
bool kuhn(int v){
    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){
    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;
}
main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    while(k--){
        scanf("%lld%lld",&x,&y);
        g[x].push_back(y);
    }
    for(x=1;x<=n;x++)
    for(y=x;y<=n;y++){
        if(check(x,y)){
            cnt+=n-y+1;
            break;
        }
    }
    printf("%lld",cnt);
}

Compilation message (stderr)

marriage.cpp:29:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main(){
      |      ^
marriage.cpp: In function 'int main()':
marriage.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |     scanf("%lld%lld%lld",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |         scanf("%lld%lld",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 48 / 100