Submission #167184

#	Time	Username	Problem	Language	Result	Execution time	Memory
167184		Dovran	Marriage questions (IZhO14_marriage)	C++11	100 / 100	985 ms	2936 KiB

marriage

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int MAXN = 34004;
int n, m, k, ts, l, r, MC[MAXN], M[MAXN];
vector < int > Adj[MAXN];
queue < int > qu;
int DFS(int v)
{
    if (M[v] == ts)
        return 0;
    M[v] = ts;
    for (int i = 0; i < (int)Adj[v].size(); i++)
        if (l <= Adj[v][i] && Adj[v][i] <= r)
            if (MC[Adj[v][i]] == -1 || DFS(MC[Adj[v][i]]))
                return MC[Adj[v][i]] = v, 1;
    return 0;
}
inline int Match()
{
    while (qu.size())
    {
        int v = qu.front();
        qu.pop(); ts ++;
        if (!DFS(v))
            return qu.push(v), 1;
    }
    return 1;
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= k; i++)
    {
        int v, u;
        scanf("%d%d", &v, &u);
        Adj[u].pb(v);
    }
    int tot = 0;
    memset(MC, -1, sizeof(MC));
    for (int i = 1; i <= m; i++)
        qu.push(i);
    for (l = 1; l <= n; l ++)
    {
        r = max(r, l); Match();
        while (r < n && qu.size())
            r ++, Match();
        if (qu.size())
            break;
        tot += n - r + 1;
        if (MC[l] != -1)
            qu.push(MC[l]), MC[l] = -1;
    }
    return !printf("%d\n", tot);
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100