Submission #96038

#	Time	Username	Problem	Language	Result	Execution time	Memory
96038		Kastanda	Marriage questions (IZhO14_marriage)	C++11	78 / 100	1591 ms	8296 KiB

marriage

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int MAXN = 34004;
struct Edge {int to, flow;};
struct Dinic
{
    int s, t, P[MAXN], D[MAXN], qu[MAXN];
    vector < int > Adj[MAXN];
    vector < Edge > E;
    inline void Add(int v, int u, int w)
    {
        Adj[v].pb(E.size());
        E.pb({u, w});
        Adj[u].pb(E.size());
        E.pb({v, 0});
    }
    inline bool BFS()
    {
        int l = 0, r = 0;
        memset(D, -1, sizeof(D));
        memset(P, 0, sizeof(P));
        qu[r ++] = s; D[s] = 0;
        while (r - l)
        {
            int v = qu[l ++];
            for (int &id : Adj[v])
                if (E[id].flow && D[E[id].to] == -1)
                {
                    D[E[id].to] = D[v] + 1;
                    if (E[id].to == t)
                        return (1);
                    qu[r ++] = E[id].to;
                }
        }
        return (0);
    }
    int DFS(int v, int flow)
    {
        if (v == t)
            return (flow);
        int Flow = 0;
        for (int i = P[v]; i < (int)Adj[v].size(); i++)
        {
            int id = Adj[v][i];
            if (E[id].flow && D[E[id].to] == D[v] + 1)
            {
                int _flow = DFS(E[id].to, min(flow, E[id].flow));
                if (!_flow)
                    swap(Adj[v][i], Adj[v][P[v]]), P[v] ++;
                E[id].flow -= _flow;
                E[id^1].flow += _flow;
                Flow += _flow; flow -= _flow;
                if (!flow) return (Flow);
            }
            else
                swap(Adj[v][i], Adj[v][P[v]]), P[v] ++;
        }
        return (Flow);
    }
    inline int MaxFlow()
    {
        int Flow = 0;
        while (BFS())
            Flow += DFS(s, INT_MAX);
        return Flow;
    }
};
int n, m, k;
Dinic G;
inline void Add(int v)
{
    v += m;
    for (int &id : G.Adj[v])
        if (G.E[id].to == G.t)
            {G.E[id].flow = 1; return ;}
    assert(0);
}
inline int Del(int v)
{
    v += m;
    for (int &id : G.Adj[v])
        if (G.E[id].to == G.t)
        {
            if (G.E[id^1].flow == 1)
            {
                int e = -1;
                for (int &idd : G.Adj[v])
                    if (G.E[idd].flow)
                        {e = idd; break;}
                assert(e != -1);
                int u = G.E[e].to;
                G.E[e].flow -= 1;
                G.E[e^1].flow += 1;
                G.E[id^1].flow = 0;
                for (int &idd : G.Adj[u])
                    if (G.E[idd].to == G.s)
                    {
                        G.E[idd].flow = 0;
                        G.E[idd^1].flow = 1;
                        return (1);
                    }
                assert(0);

            }
            else
                {G.E[id].flow = 0; return (0);}
        }
    assert(0);
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    int source = 0, sink = n + m + 1;
    G.s = source; G.t = sink;
    for (int i = 1; i <= m; i++)
        G.Add(source, i, 1);
    for (int i = 1; i <= n; i++)
        G.Add(m + i, sink, 0);
    for (int i = 1; i <= k; i++)
    {
        int v, u;
        scanf("%d%d", &v, &u);
        G.Add(u, v + m, 1);
    }
    int r = 0, Flow = 0;
    int tot = 0;
    for (int l = 1; l <= n; l ++)
    {
        while (r < l)
            r ++, Add(r);
        Flow += G.MaxFlow();
        while (r < n && Flow < m)
            r ++, Add(r), Flow += G.MaxFlow();
        if (Flow < m)
            break;
        tot += n - r + 1;
        Flow -= Del(l);
    }
    return !printf("%d\n", tot);
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:113: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:123: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: 78 / 100