제출 #171833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
171833		VEGAnn	결혼 문제 (IZhO14_marriage)	C++14	64 / 100	1580 ms	3568 KiB

marriage

#include <bits/stdc++.h>
#define sz(x) ((us)x.size())
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define pii pair<us, us>
#define pi3 pair<pii, us>
#define MP3(a,b,c) MP(MP(a, b), c)
using namespace std;
typedef unsigned short us;
const us oo = 32000;
const us N = 32100;
const us K = 110;
const us PW = 20;

struct edge{
    us y;
    bool psh;

    edge(us _y, bool _p): y(_y), psh(_p) {}
};

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

void add_edge(us x, us y){

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

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

}

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

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

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

    while (sz(q)){
        us 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(us 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;
        us 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(us l, us r){

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

    us flow = 0;

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

    while (bfs(l, r)){
        fill(ptr, ptr + t + 1, 0);
        bool 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 (us i = 0; i < k; i++){
        us x, y; cin >> y >> x;
        x--; y--;
        add_edge(x, m + y);
    }

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

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

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

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

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

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

        int nm = g[t][l];

        if (edges[nm].psh) continue;

        us pr = -1, cr = m + l;
        for (us it = 0; it < sz(g[cr]); it++){
            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: 64 / 100