oj.uz

답안 #171855

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171855 2019-12-30T13:42:48 Z VEGAnn 결혼 문제 (IZhO14_marriage) C++14
6 / 100
 91 ms 8168 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define y first
#define psh second
#define edge pair<int, bool>
#define pi3 pair<pii, int>
#define MP3(a,b,c) MP(MP(a, b), c)
using namespace std;
const int oo = 1e9;
const int N = 32100;
const int K = 110;
const int PW = 20;

vector<edge> edges;
queue<int> q;
vector<int> g[N];
int ans = 0, s, t, n, m, k, dst[N], ptr[N];

void add_edge(int x, int y){

    g[x].PB(sz(edges));
    edges.PB(edge(y, 0));

    g[y].PB(sz(edges));
    edges.PB(edge(x, 1));

}

bool bad(int l, int r, int v){
    if (v == s || v == t || v < m) return 0;
    return !(m + l <= v && v <= m + r);
}

bool bfs(int l, int r){
    fill(dst, dst + t + 1, oo);

    dst[s] = 0;
    while (sz(q)) q.pop();
    q.push(s);

    while (sz(q)){
        int v = q.front(); q.pop();

        for (int nm : g[v]){
            edge u = edges[nm];
            if (!bad(l, r, u.y) && !u.psh && dst[u.y] > dst[v] + 1){
                dst[u.y] = dst[v] + 1;
                q.push(u.y);
            }
        }
    }

    return (dst[t] < oo);
}

bool dfs(int v, bool pshd){
    if (pshd == 0) return 0;
    if (v == t) return pshd;
    for (; ptr[v] < sz(g[v]); ptr[v]++){
        int nm = g[v][ptr[v]];
        edge u = edges[nm];
        if (dst[u.y] != dst[v] + 1) continue;
        int nw = dfs(u.y, min(pshd, !u.psh));
        if (nw){
            edges[nm].psh = 1;
            edges[nm ^ 1].psh = 0;
            return nw;
        }
    }
    return 0;
}

bool ok(int l, int r){

    if (r - l + 1 < m) return 0;

    int flow = 0;

    for (int i = 0; i < m; i++) {
        int nm = g[s][i];
        flow += edges[nm].psh;
    }

    while (bfs(l, r)){
        fill(ptr, ptr + t + 1, 0);
        int pshd = dfs(s, oo);
        while (pshd > 0){
            flow += pshd;
            pshd = dfs(s, oo);
        }
    }

    return (flow == m);
}

bool kok(int l, int r){

    if (r - l + 1 < m) return 0;

    for (int it = 0; it < sz(edges); it += 2){
        edges[it].psh = 0;
        edges[it ^ 1].psh = 1;
    }

    int flow = 0;

    while (bfs(l, r)){
        fill(ptr, ptr + t + 1, 0);
        int pshd = dfs(s, oo);
        while (pshd > 0){
            flow += pshd;
            pshd = dfs(s, oo);
        }
    }

    return (flow == m);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m >> k;

    for (int i = 0; i < k; i++){
        int x, y; cin >> y >> x;
        x--; y--;
        add_edge(x, m + y);
    }

    s = n + m;
    t = n + m + 1;

    for (int i = 0; i < m; i++)
        add_edge(s, i);

    for (int i = 0; i < n; i++)
        add_edge(i + m, t);

    for (int l = 0, r = 0; l < n; l++){

        if (l + m - 1 >= n) break;

        if (l == 0){
            int lf = m - 1, rt = n - 1;
            while (lf < rt){
                int md = (lf + rt) >> 1;
                if (kok(l, md))
                    rt = md;
                else lf = md + 1;
            }
            if (lf >= n) break;

            if (!kok(l, r)) return -1;

            r = lf;
            kok(l, r);
            ans += n - r;
        } else {

            while (r < n && !ok(l, r))
                r++;
            if (r >= n) break;
            ans += n - r;

        }

        int nm = g[t][l];

        if (edges[nm].psh) continue;

        int pr = -1, cr = m + l;
        for (int it = 0; it < sz(g[cr]); it++){
            int nm = g[cr][it];
            edge ed = edges[nm];

            if (ed.y != t && !ed.psh){
                pr = ed.y;
                break;
            }
        }

        nm = g[s][pr];
        edges[nm].psh = 0;
        edges[nm ^ 1].psh = 1;
    }

    cout << ans;

    return 0;
}

Subtask #1
6.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1016 KB Execution failed because the return code was nonzero
2 Runtime error 3 ms 1144 KB Execution failed because the return code was nonzero
3 Runtime error 2 ms 1016 KB Execution failed because the return code was nonzero
4 Runtime error 2 ms 1016 KB Execution failed because the return code was nonzero
5 Runtime error 2 ms 1016 KB Execution failed because the return code was nonzero
6 Runtime error 3 ms 1148 KB Execution failed because the return code was nonzero
7 Runtime error 2 ms 1144 KB Execution failed because the return code was nonzero
8 Correct 2 ms 1144 KB Output is correct
9 Runtime error 2 ms 1016 KB Execution failed because the return code was nonzero
10 Correct 3 ms 1016 KB Output is correct
11 Runtime error 3 ms 1144 KB Execution failed because the return code was nonzero
12 Runtime error 3 ms 1144 KB Execution failed because the return code was nonzero
13 Correct 3 ms 1144 KB Output is correct
14 Runtime error 3 ms 1144 KB Execution failed because the return code was nonzero
15 Runtime error 3 ms 1144 KB Execution failed because the return code was nonzero
16 Runtime error 3 ms 1144 KB Execution failed because the return code was nonzero
17 Runtime error 3 ms 1016 KB Execution failed because the return code was nonzero
18 Runtime error 3 ms 1016 KB Execution failed because the return code was nonzero
19 Runtime error 3 ms 1144 KB Execution failed because the return code was nonzero
20 Runtime error 3 ms 1144 KB Execution failed because the return code was nonzero
21 Runtime error 3 ms 1144 KB Execution failed because the return code was nonzero
22 Runtime error 3 ms 1144 KB Execution failed because the return code was nonzero
23 Runtime error 3 ms 1144 KB Execution failed because the return code was nonzero
24 Runtime error 3 ms 1148 KB Execution failed because the return code was nonzero
25 Runtime error 8 ms 1656 KB Execution failed because the return code was nonzero
26 Runtime error 5 ms 1272 KB Execution failed because the return code was nonzero
27 Runtime error 3 ms 1144 KB Execution failed because the return code was nonzero
28 Runtime error 3 ms 1144 KB Execution failed because the return code was nonzero
29 Runtime error 6 ms 1528 KB Execution failed because the return code was nonzero
30 Runtime error 5 ms 1528 KB Execution failed because the return code was nonzero
31 Runtime error 32 ms 2932 KB Execution failed because the return code was nonzero
32 Runtime error 7 ms 1404 KB Execution failed because the return code was nonzero
33 Runtime error 4 ms 1148 KB Execution failed because the return code was nonzero
34 Runtime error 4 ms 1272 KB Execution failed because the return code was nonzero
35 Runtime error 37 ms 4552 KB Execution failed because the return code was nonzero
36 Runtime error 32 ms 4564 KB Execution failed because the return code was nonzero
37 Runtime error 48 ms 3176 KB Execution failed because the return code was nonzero
38 Runtime error 41 ms 4932 KB Execution failed because the return code was nonzero
39 Runtime error 9 ms 2036 KB Execution failed because the return code was nonzero
40 Runtime error 39 ms 2164 KB Execution failed because the return code was nonzero
41 Runtime error 32 ms 2416 KB Execution failed because the return code was nonzero
42 Runtime error 22 ms 2928 KB Execution failed because the return code was nonzero
43 Runtime error 31 ms 4584 KB Execution failed because the return code was nonzero
44 Runtime error 48 ms 5044 KB Execution failed because the return code was nonzero
45 Runtime error 54 ms 3948 KB Execution failed because the return code was nonzero
46 Runtime error 91 ms 6076 KB Execution failed because the return code was nonzero
47 Runtime error 63 ms 8164 KB Execution failed because the return code was nonzero
48 Runtime error 57 ms 5992 KB Execution failed because the return code was nonzero
49 Runtime error 85 ms 8168 KB Execution failed because the return code was nonzero
50 Runtime error 13 ms 3304 KB Execution failed because the return code was nonzero