Submission #96042

#	Time	Username	Problem	Language	Result	Execution time	Memory
96042		Kastanda	Marriage questions (IZhO14_marriage)	C++11	96 / 100	1574 ms	9116 KiB

marriage

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int MAXN = 34004;
struct Edge {int to, flow;};
int s, t, P[MAXN], D[MAXN], qu[MAXN];
vector < int > Adj[MAXN];
vector < Edge > E;
int ptr, mm;
inline void AddEdge(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 i = 0; i < (int)Adj[v].size(); i++)
        {
            int id = Adj[v][i];
            if (mm < E[id].to && E[id].to <= ptr)
                swap(Adj[v][i], Adj[v].back()), Adj[v].pop_back(), i --;
            else 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;
vector < int > vec[MAXN];
inline void Add(int v)
{
    AddEdge(v + m, t, 1);
    for (int &u : vec[v])
        AddEdge(u, v + m, 1);
}
inline int Del(int v)
{
    v += m;
    for (int &id : Adj[v])
        if (E[id].to == t)
        {
            if (E[id^1].flow == 1)
            {
                int e = -1;
                for (int &idd : Adj[v])
                    if (E[idd].flow)
                        {e = idd; break;}
                assert(e != -1);
                int u = E[e].to;
                E[e].flow -= 1;
                E[e^1].flow += 1;
                E[id^1].flow = 0;
                for (int &idd : Adj[u])
                    if (E[idd].to == s)
                    {
                        E[idd].flow = 0;
                        E[idd^1].flow = 1;
                        return (1);
                    }
                assert(0);

            }
            else
                {E[id].flow = 0; return (0);}
        }
    assert(0);
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    int source = 0, sink = n + m + 1;
    s = source; t = sink;
    for (int i = 1; i <= m; i++)
        AddEdge(source, i, 1);
    for (int i = 1; i <= k; i++)
    {
        int v, u;
        scanf("%d%d", &v, &u);
        vec[v].pb(u);
        //AddEdge(u, v + m, 1);
    }
    srand(time(0));
    for (int i = 1; i <= n; i++)
        random_shuffle(vec[i].begin(), vec[i].end());

    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:114: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:122: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: 96 / 100