Submission #90679

#	Time	Username	Problem	Language	Result	Execution time	Memory
90679		popovicirobert	Marriage questions (IZhO14_marriage)	C++14	94 / 100	1574 ms	7336 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 {
    set <int> g[MAXM + 1];
    vector <int> vis, l, r;
    int n, now;
    int ans;
    inline void init(int _n) {
        n = _n;
        l.resize(n + 1);
        r.resize(n + 1);
        vis.resize(n + 1);
        ans = now = 0;
    }
    inline void addEdge(int x, int y) {
        g[x].insert(y);
    }
    inline void delEdge(int x, int y) {
        g[x].erase(g[x].find(y));
        if(l[x] == y) {
            l[x] = r[y] = 0;
            ans--;
        }
    }
    bool match(int nod) {
        for(auto it : g[nod]) {
            if(r[it] == 0) {
                l[nod] = it;
                r[it] = nod;
                return 1;
            }
        }
        vis[nod] = now;
        for(auto it : g[nod]) {
            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: 94 / 100