Submission #90681

#	Time	Username	Problem	Language	Result	Execution time	Memory
90681		popovicirobert	Marriage questions (IZhO14_marriage)	C++14	100 / 100	597 ms	4220 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;
const int MAXM = 2000;

struct Match {
    vector <int> g[MAXN + 1];
    vector <int> vis, l, r, pos;
    int n, now;
    int ans;
    inline void init(int _n) {
        n = _n;
        l.resize(n + 1);
        r.resize(n + 1);
        vis.resize(n + 1);
        pos.resize(n + 1);
        ans = now = 0;
    }
    inline void addEdge(int x, int y) {
        g[x].push_back(y);
    }
    inline void delEdge(int x, int y) {
        int sz = g[x].size();
        while(pos[x] < sz && g[x][pos[x]] == y) {
            pos[x]++;
        }
        if(l[x] == y) {
            l[x] = r[y] = 0;
            ans--;
        }
    }
    bool match(int nod) {
        int sz = g[nod].size();
        for(int i = pos[nod]; i < sz; i++) {
            auto it = g[nod][i];
            if(r[it] == 0) {
                l[nod] = it;
                r[it] = nod;
                return 1;
            }
        }
        vis[nod] = now;
        for(int i = pos[nod]; i < sz; i++) {
            auto it = g[nod][i];
            if(vis[r[it]] != now && match(r[it])) {
                l[nod] = it;
                r[it] = nod;
                return 1;
            }
        }
        return 0;
    }
    inline int solve(int m) {
        bool flag = 1;
        int i;
        while(flag && ans < m) {
            flag = 0;
            now++;
            for(i = 1; i <= m; i++) {
                if(l[i] == 0) {
                    flag |= match(i);
                    ans += (l[i] > 0);
                }
            }
        }
        return ans;
    }
}M;

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);
    }
    M.init(n + m);
    int pos = 1, mx = 0;
    int ans = 0;
    for(i = 1; i <= n; i++) {
        bool ok = 0;
        while(M.solve(m) < m && pos <= n) {
            if(mx < pos) {
                for(auto it : g[pos]) {
                    M.addEdge(it, pos + m);
                }
            }
            mx = max(mx, pos);
            pos++;
            ok = 1;
        }
        pos -= ok;
        if(M.ans == m) {
            ans += n - pos + 1;
        }
        for(auto it : g[i]) {
            M.delEdge(it, i + m);
        }
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

• Subtask 1: 100 / 100