Submission #90671

#	Time	Username	Problem	Language	Result	Execution time	Memory
90671		popovicirobert	Marriage questions (IZhO14_marriage)	C++14	72 / 100	1587 ms	23556 KiB

marriage

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = 30000;

struct MaxFlow {

    const int INF = 1e9;

    struct Edge {
        int nod, id1, id2;
    };

    vector < vector <Edge> > g;
    vector <Edge> from;
    vector <int> cap, vis;
    int n, m;
    int sink, dest;
    int now, ans;

    inline void init(int _n, int _sink, int _dest) {
        n = _n, sink = _sink, dest = _dest;
        m = 0;
        g.resize(n + 1);
        from.resize(n + 1);
        vis.resize(n + 1);
        ans = now = 0;
    }

    inline void addEdge(int x, int y, int c) {
        if(mp[{y, x}]) {
            return ;
        }

        g[x].push_back({y, m, m + 1});
        cap.push_back(c);
        mp[{x, y}] = m;

        g[y].push_back({x, m + 1, m});
        cap.push_back(0);
        mp[{y, x}] = m + 1;

        m += 2;
    }

    inline bool bfs() {
        queue <int> Q;
        now++;
        Q.push(sink);
        vis[sink] = now;
        while(Q.size()) {
            int nod = Q.front();
            Q.pop();
            for(auto it : g[nod]) {
                if(vis[it.nod] != now && cap[it.id1] > 0) {
                    Q.push(it.nod);
                    from[it.nod] = {nod, it.id1, it.id2};
                    vis[it.nod] = now;
                }
            }
        }
        return vis[dest] == now;
    }

    inline int flow() {
        while(bfs()) {
            int nod = dest;
            int mn = INF;
            while(nod != sink) {
                mn = min(mn, cap[from[nod].id1]);
                nod = from[nod].nod;
            }
            nod = dest;
            while(nod != sink) {
                cap[from[nod].id1] -= mn;
                cap[from[nod].id2] += mn;
                nod = from[nod].nod;
            }
            ans += mn;
        }
        return ans;
    }

    map < pair <int, int>, int > mp;
    inline void delEdge(int x, int y) {
        if(x > n) {
            swap(x, y);
        }
        int id1 = mp[{x, y}];
        int id2 = id1 + 1;
        if(cap[id1] == 0) {
            ans--;
            cap[mp[{sink, x}]] = cap[mp[{y, dest}]] = 1;
        }
        cap[mp[{x, sink}]] = cap[mp[{dest, y}]] = 0;
        cap[id1] = cap[id2] = 0;
    }

};

vector <int> g[MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m, k;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for(i = 1; i <= k; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
    }
    MaxFlow net;
    net.init(n + m + 2, n + m + 1, n + m + 2);
    for(i = 1; i <= n; i++) {
        net.addEdge(net.sink, i, 1);
    }
    for(i = 1; i <= m; i++) {
        net.addEdge(i + n, net.dest, 1);
    }
    int pos = 1;
    ll ans = 0;
    for(i = 1; i <= n; i++) {
        bool ok = 0;
        while(net.flow() < m && pos <= n) {
            for(auto it : g[pos]) {
                net.addEdge(pos, it + n, 1);
            }
            pos++;
            ok = 1;
        }
        pos -= ok;
        if(net.ans == m) {
            ans += n - pos + 1;
        }
        for(auto it : g[i]) {
            net.delEdge(i, it + n);
        }
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

• Subtask 1: 72 / 100