답안 #96042 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96042	2019-02-05T11:23:44 Z	Kastanda	결혼 문제 (IZhO14_marriage)	C++11	96 / 100	1500 ms	9116 KB

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

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2168 KB	Output is correct
2	Correct	4 ms	2168 KB	Output is correct
3	Correct	3 ms	2168 KB	Output is correct
4	Correct	4 ms	2168 KB	Output is correct
5	Correct	4 ms	2168 KB	Output is correct
6	Correct	4 ms	2168 KB	Output is correct
7	Correct	4 ms	2216 KB	Output is correct
8	Correct	3 ms	2168 KB	Output is correct
9	Correct	3 ms	2168 KB	Output is correct
10	Correct	3 ms	2172 KB	Output is correct
11	Correct	3 ms	2168 KB	Output is correct
12	Correct	3 ms	2168 KB	Output is correct
13	Correct	3 ms	2168 KB	Output is correct
14	Correct	4 ms	2168 KB	Output is correct
15	Correct	4 ms	2168 KB	Output is correct
16	Correct	3 ms	2168 KB	Output is correct
17	Correct	4 ms	2168 KB	Output is correct
18	Correct	3 ms	2168 KB	Output is correct
19	Correct	9 ms	2424 KB	Output is correct
20	Correct	8 ms	2168 KB	Output is correct
21	Correct	6 ms	2168 KB	Output is correct
22	Correct	6 ms	2172 KB	Output is correct
23	Correct	7 ms	2296 KB	Output is correct
24	Correct	6 ms	2296 KB	Output is correct
25	Correct	42 ms	2784 KB	Output is correct
26	Correct	26 ms	2296 KB	Output is correct
27	Correct	12 ms	2296 KB	Output is correct
28	Correct	15 ms	2296 KB	Output is correct
29	Correct	16 ms	2680 KB	Output is correct
30	Correct	16 ms	2680 KB	Output is correct
31	Correct	388 ms	3824 KB	Output is correct
32	Correct	57 ms	2552 KB	Output is correct
33	Correct	26 ms	2296 KB	Output is correct
34	Correct	39 ms	2404 KB	Output is correct
35	Correct	370 ms	5504 KB	Output is correct
36	Correct	259 ms	5552 KB	Output is correct
37	Correct	1160 ms	4120 KB	Output is correct
38	Correct	101 ms	5848 KB	Output is correct
39	Correct	542 ms	3316 KB	Output is correct
40	Correct	336 ms	3188 KB	Output is correct
41	Correct	513 ms	3568 KB	Output is correct
42	Correct	294 ms	4188 KB	Output is correct
43	Correct	272 ms	5828 KB	Output is correct
44	Correct	402 ms	5836 KB	Output is correct
45	Correct	972 ms	5156 KB	Output is correct
46	Execution timed out	1561 ms	6864 KB	Time limit exceeded
47	Correct	706 ms	9116 KB	Output is correct
48	Correct	715 ms	6788 KB	Output is correct
49	Execution timed out	1574 ms	6488 KB	Time limit exceeded
50	Correct	1404 ms	4720 KB	Output is correct

답안 #96042

Compilation message

Subtask #1 96.0 / 100.0

Subtask #1
96.0 / 100.0