Submission #92706

#	Time	Username	Problem	Language	Result	Execution time	Memory
92706		Aydarov03	Marriage questions (IZhO14_marriage)	C++14	100 / 100	347 ms	2316 KiB

marriage

#include <bits/stdc++.h>
using namespace std;
const int M = 2e3 + 5;

vector <int> g[M];
queue <int> q;
int used[M] , cnt = 1 , mt[30005] , l , r , ans;

bool khun( int v )
{
    if( used[v] == cnt )
        return false;
    used[v] = cnt;

    for(auto to : g[v])
    {
        if(to < l)continue;
        if(to > r)break;

        if( mt[to] == -1 || khun( mt[to] ) )
        {
            mt[to] = v;
            return true;
        }
    }
    return false;
}


bool check()
{
    while( !q.empty() )
    {
        int v = q.front();
        q.pop();
        cnt++;
        if( !khun(v) )
        {
            q.push(v);
            return false;
        }
    }

    return true;
}


main()
{
    int n , m , k;
    cin >> n >> m >> k;

    for(int i = 1; i <= k; i++)
    {
        int a , b;
        scanf("%d %d" , &a , &b);
        g[b].push_back( a );
    }

	memset(mt, -1, sizeof mt);
    for(int i = 1; i <= m; i++){
        sort( g[i].begin() , g[i].end() );
        q.push(i);
    }

    r = 1;

    for(int i = 1; i <= n; i++)
    {
        l = i;
        while(r <= n && !check() )
            r++;

        ans += (n - r + 1);

        if( mt[i] != -1 )
        {
            q.push( mt[i] );
            mt[i] = -1;
        }
    }

    cout << ans;

}

Compilation message (stderr)

marriage.cpp:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
marriage.cpp: In function 'int main()':
marriage.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d" , &a , &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100