oj.uz

Submission #90677

# Submission time Handle Problem Language Result Execution time Memory
90677 2018-12-23T13:33:04 Z popovicirobert Marriage questions (IZhO14_marriage) C++14
82 / 100
 1500 ms 11644 KB 
#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 < vector <int> > g;
    vector <int> vis, l, r;
    bitset <MAXN * MAXM> mp;
    int n, now;
    int ans;
    inline void init(int _n) {
        n = _n;
        g.resize(n + 1);
        l.resize(n + 1);
        r.resize(n + 1);
        vis.resize(n + 1);
        ans = now = 0;
    }
    inline int get(int x, int y) {
        return (x - 1) * MAXN + y - 1;
    }
    inline void addEdge(int x, int y) {
        g[x].push_back(y);
    }
    inline void delEdge(int x, int y) {
        mp[get(x, y)] = 1;
        if(l[x] == y) {
            l[x] = r[y] = 0;
        }
    }
    bool match(int nod) {
        for(auto it : g[nod]) {
            if(r[it] == 0 && mp[get(nod, it)] == 0) {
                l[nod] = it;
                r[it] = nod;
                return 1;
            }
        }
        vis[nod] = now;
        for(auto it : g[nod]) {
            if(mp[get(nod, it)] == 0 && 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) {
            flag = 0;
            now++;
            for(i = 1; i <= m; i++) {
                if(l[i] == 0) {
                    flag |= match(i);
                }
            }
        }
        ans = 0;
        for(i = 1; i <= m; 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
82.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8312 KB Output is correct
2 Correct 8 ms 8436 KB Output is correct
3 Correct 7 ms 8504 KB Output is correct
4 Correct 8 ms 8504 KB Output is correct
5 Correct 8 ms 8548 KB Output is correct
6 Correct 7 ms 8548 KB Output is correct
7 Correct 8 ms 8564 KB Output is correct
8 Correct 7 ms 8564 KB Output is correct
9 Correct 8 ms 8608 KB Output is correct
10 Correct 8 ms 8608 KB Output is correct
11 Correct 7 ms 8608 KB Output is correct
12 Correct 7 ms 8608 KB Output is correct
13 Correct 8 ms 8624 KB Output is correct
14 Correct 8 ms 8624 KB Output is correct
15 Correct 8 ms 8624 KB Output is correct
16 Correct 8 ms 8624 KB Output is correct
17 Correct 7 ms 8632 KB Output is correct
18 Correct 7 ms 8632 KB Output is correct
19 Correct 10 ms 8680 KB Output is correct
20 Correct 8 ms 8680 KB Output is correct
21 Correct 8 ms 8680 KB Output is correct
22 Correct 8 ms 8680 KB Output is correct
23 Correct 8 ms 8700 KB Output is correct
24 Correct 9 ms 8700 KB Output is correct
25 Correct 46 ms 8828 KB Output is correct
26 Correct 14 ms 8828 KB Output is correct
27 Correct 11 ms 8828 KB Output is correct
28 Correct 9 ms 8828 KB Output is correct
29 Correct 27 ms 8828 KB Output is correct
30 Correct 26 ms 8828 KB Output is correct
31 Correct 462 ms 9376 KB Output is correct
32 Correct 57 ms 9376 KB Output is correct
33 Correct 15 ms 9376 KB Output is correct
34 Correct 21 ms 9376 KB Output is correct
35 Correct 539 ms 9764 KB Output is correct
36 Correct 444 ms 9764 KB Output is correct
37 Correct 1465 ms 9764 KB Output is correct
38 Correct 1195 ms 9980 KB Output is correct
39 Correct 880 ms 9980 KB Output is correct
40 Correct 701 ms 9980 KB Output is correct
41 Correct 990 ms 9980 KB Output is correct
42 Execution timed out 1569 ms 9980 KB Time limit exceeded
43 Execution timed out 1565 ms 9980 KB Time limit exceeded
44 Execution timed out 1579 ms 10364 KB Time limit exceeded
45 Execution timed out 1570 ms 10748 KB Time limit exceeded
46 Execution timed out 1548 ms 11516 KB Time limit exceeded
47 Execution timed out 1577 ms 11516 KB Time limit exceeded
48 Execution timed out 1578 ms 11516 KB Time limit exceeded
49 Execution timed out 1559 ms 11644 KB Time limit exceeded
50 Execution timed out 1567 ms 11644 KB Time limit exceeded