oj.uz

Submission #96041

# Submission time Handle Problem Language Result Execution time Memory
96041 2019-02-05T11:06:51 Z Kastanda Marriage questions (IZhO14_marriage) C++11
78 / 100
 1500 ms 3832 KB 
#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];
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 ++];
        for (int id = head[v]; ~id; id = nxt[id])
            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;
inline void Add(int v)
{
    flow[head[v + m]] = 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 (; ~e; e = nxt[e])
    {
        flow[e^1] = 0;
        if (flow[e])
            break;
    }
    assert(e != -1);
    int u = to[e];
    flow[e] = 0;
    flow[head[u]] = 0;
    flow[head[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);
        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);
    for (int i = 1; i <= n; i++)
        AddEdge(m + i, sink, 0);
    int r = 0, Flow = 0;
    int tot = 0;
    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);
    }
    return !printf("%d\n", tot);
}

Compilation message

marriage.cpp: In function 'int main()':
marriage.cpp:87: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:91: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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1656 KB Output is correct
2 Correct 3 ms 1656 KB Output is correct
3 Correct 3 ms 1656 KB Output is correct
4 Correct 3 ms 1656 KB Output is correct
5 Correct 3 ms 1656 KB Output is correct
6 Correct 3 ms 1656 KB Output is correct
7 Correct 3 ms 1656 KB Output is correct
8 Correct 3 ms 1656 KB Output is correct
9 Correct 3 ms 1656 KB Output is correct
10 Correct 3 ms 1656 KB Output is correct
11 Correct 3 ms 1656 KB Output is correct
12 Correct 3 ms 1656 KB Output is correct
13 Correct 3 ms 1656 KB Output is correct
14 Correct 3 ms 1656 KB Output is correct
15 Correct 3 ms 1656 KB Output is correct
16 Correct 3 ms 1656 KB Output is correct
17 Correct 3 ms 1656 KB Output is correct
18 Correct 3 ms 1656 KB Output is correct
19 Correct 8 ms 1656 KB Output is correct
20 Correct 5 ms 1656 KB Output is correct
21 Correct 4 ms 1656 KB Output is correct
22 Correct 4 ms 1656 KB Output is correct
23 Correct 5 ms 1656 KB Output is correct
24 Correct 4 ms 1660 KB Output is correct
25 Correct 171 ms 1912 KB Output is correct
26 Correct 24 ms 1656 KB Output is correct
27 Correct 8 ms 1656 KB Output is correct
28 Correct 8 ms 1656 KB Output is correct
29 Correct 23 ms 1784 KB Output is correct
30 Correct 21 ms 1784 KB Output is correct
31 Execution timed out 1556 ms 2424 KB Time limit exceeded
32 Correct 78 ms 1784 KB Output is correct
33 Correct 22 ms 1656 KB Output is correct
34 Correct 21 ms 1656 KB Output is correct
35 Correct 1067 ms 3280 KB Output is correct
36 Correct 769 ms 2936 KB Output is correct
37 Execution timed out 1582 ms 2424 KB Time limit exceeded
38 Correct 903 ms 3320 KB Output is correct
39 Correct 461 ms 2044 KB Output is correct
40 Correct 1155 ms 2168 KB Output is correct
41 Execution timed out 1575 ms 2168 KB Time limit exceeded
42 Correct 1340 ms 2424 KB Output is correct
43 Execution timed out 1575 ms 2684 KB Time limit exceeded
44 Execution timed out 1573 ms 3320 KB Time limit exceeded
45 Execution timed out 1563 ms 2680 KB Time limit exceeded
46 Execution timed out 1567 ms 3704 KB Time limit exceeded
47 Execution timed out 1578 ms 3832 KB Time limit exceeded
48 Execution timed out 1582 ms 3704 KB Time limit exceeded
49 Execution timed out 1583 ms 3832 KB Time limit exceeded
50 Execution timed out 1559 ms 2268 KB Time limit exceeded