Submission #96044

#	Time	Username	Problem	Language	Result	Execution time	Memory
96044		Kastanda	Marriage questions (IZhO14_marriage)	C++11	100 / 100	1314 ms	5812 KiB

marriage

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int MAXN = 34004, MAXM = 268900;
int s, t, P[MAXN], qu[MAXN];
int ts, to[MAXM], flow[MAXM];
int head[MAXN], nxt[MAXM];
int ptr, mm;
inline void AddEdge(int v, int u, int w)
{
    nxt[ts] = head[v]; head[v] = ts;
    to[ts] = u; flow[ts] = w; ts ++;
    nxt[ts] = head[u]; head[u] = ts;
    to[ts] = v; flow[ts] = 0; ts ++;
}
inline bool BFS()
{
    int l = 0, r = 0;
    memset(P, -1, sizeof(P));
    qu[r ++] = s;
    while (r - l)
    {
        int v = qu[l ++];
        while (~head[v] && mm < to[head[v]] && to[head[v]] <= ptr)
            head[v] = nxt[head[v]];
        for (int id = head[v], p = id; ~id; p = id, id = nxt[id])
        {
            if (mm < to[id] && to[id] <= ptr)
                nxt[p] = nxt[id], id = p;
            else if (flow[id] && P[to[id]] == -1)
            {
                P[to[id]] = id;
                if (to[id] == t)
                    return (1);
                qu[r ++] = to[id];
            }
        }
    }
    return (0);
}
inline int MaxFlow()
{
    int Flow = 0;
    while (BFS())
    {
        int v = t, _flow = INT_MAX;
        while (v != s)
            _flow = min(_flow, flow[P[v]]), v = to[P[v]^1];
        Flow += _flow; v = t;
        while (v != s)
        {
            flow[P[v]] -= _flow;
            flow[P[v]^1] += _flow;
            v = to[P[v]^1];
        }
    }
    return Flow;
}
int n, m, k, source, sink;
int tff[2003];
vector < int > vec[MAXN];
inline void Add(int v)
{
    for (int &u : vec[v])
        AddEdge(u, v + m, 1);
    AddEdge(v + m, sink, 1);
}
inline int Del(int v)
{
    v += m;
    if (flow[head[v]])
    {
        flow[head[v]] = 0;
        //for (int e = head[v]; ~e; e = nxt[e])
            //flow[e^1] = 0;
        return (0);
    }
    flow[head[v]^1] = 0;
    int e = head[v];
    for (; !flow[e]; e = nxt[e]);
    int u = to[e];
    flow[e] = 0;
    flow[tff[u]] = 0;
    flow[tff[u]^1] = 1;
    return (1);
}
int main()
{
    memset(head, -1, sizeof(head));
    memset(nxt, -1, sizeof(nxt));

    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= k; i++)
    {
        int v, u;
        scanf("%d%d", &v, &u);
        vec[v].pb(u);
        //AddEdge(u, v + m, 1);
    }
    source = 0; sink = n + m + 1;
    s = source; t = sink;
    for (int i = 1; i <= m; i++)
        AddEdge(source, i, 1), tff[i] = ts - 1;
    //for (int i = 1; i <= n; i++)
        //AddEdge(m + i, sink, 0);
    int r = 0, Flow = 0;
    int tot = 0;
    ptr = mm = m;
    for (int l = 1; l <= n; l ++)
    {
        while (r < l)
            r ++, Add(r);
        Flow += MaxFlow();
        while (r < n && Flow < m)
            r ++, Add(r), Flow += MaxFlow();
        if (Flow < m)
            break;
        tot += n - r + 1;
        Flow -= Del(l);
        ptr ++;
    }
    return !printf("%d\n", tot);
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:92: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:96: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