Submission #341243

#	Time	Username	Problem	Language	Result	Execution time	Memory
341243		juggernaut	Marriage questions (IZhO14_marriage)	C++14	100 / 100	817 ms	2156 KiB

marriage

#include<bits/stdc++.h>
using namespace std;
int n,m,qq,mt[30005],GL,GR,vis[2005],timer;
vector<int>g[2005];
queue<int>q;
bool kuhn(int v){
    if(vis[v]==timer)return false;
    vis[v]=timer;
    for(int to:g[v]){
        if(to<GL||to>GR)continue;
        if(!mt[to]||kuhn(mt[to])){
            mt[to]=v;
            return true;
        }
    }
    return false;
}
bool check(){
    while(!q.empty()){
        int v=q.front();
        q.pop();
        timer++;
        if(!kuhn(v)){
            q.push(v);
            return false;
        }
    }
    return true;
}
int main(){
    scanf("%d%d%d",&n,&m,&qq);
    while(qq--){
        int x,y;
        scanf("%d%d",&x,&y);
        g[y].push_back(x);
    }
    for(int i=1;i<=m;i++)q.push(i);
    int ans=0;
    GR=1;
    for(GL=1;GL<=n;GL++){
        while(GR<=n&&!check())GR++;
        ans+=n-GR+1;
        if(mt[GL]){
            q.push(mt[GL]);
            mt[GL]=0;
        }
    }
    cout<<ans;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100