oj.uz

Submission #90672

# Submission time Handle Problem Language Result Execution time Memory
90672 2018-12-23T12:49:52 Z popovicirobert Marriage questions (IZhO14_marriage) C++14
0 / 100
 30 ms 4612 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;

struct Match {
    vector < vector <int> > g;
    vector <int> vis, l, r;
    map < pair <int, int>, int > mp;
    int n, now;
    int ans;
    inline void init(int _n) {
        g.resize(n + 1);
        l.resize(n + 1);
        r.resize(n + 1);
        vis.resize(n + 1);
        n = _n;
        ans = now = 0;
    }
    inline void addEdge(int x, int y) {
        g[x].push_back(y);
    }
    inline void delEdge(int x, int y) {
        mp[{x, y}] = 1;
    }
    bool match(int nod) {
        for(auto it : g[nod]) {
            if(r[it] == 0 && mp[{nod, it}] == 0) {
                l[nod] = it;
                r[it] = nod;
                return 1;
            }
        }
        vis[nod] = now;
        for(auto it : g[nod]) {
            if(mp[{nod, it}] == 0 && vis[r[it]] != now && match(r[it])) {
                l[nod] = it;
                r[it] = nod;
                return 1;
            }
        }
        return 0;
    }
    inline int solve() {
        bool flag = 1;
        int i;
        while(flag) {
            flag = 0;
            for(i = 1; i <= n; i++) {
                if(l[i] == 0) {
                    flag |= match(i);
                }
            }
        }
        for(i = 1; i <= n; 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);
    }
    Match M;
    M.init(n + m);
    int pos = 1;
    ll ans = 0;
    for(i = 1; i <= n; i++) {
        bool ok = 0;
        while(M.solve() < m && pos <= n) {
            for(auto it : g[pos]) {
                M.addEdge(pos, it + n);
            }
            pos++;
            ok = 1;
        }
        pos -= ok;
        if(M.ans == m) {
            ans += n - pos + 1;
        }
        for(auto it : g[i]) {
            M.delEdge(i, it + n);
        }
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 3 ms 1924 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 2104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 4 ms 2228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 3 ms 2248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 4 ms 2252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 3 ms 2312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 2312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 3 ms 2312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3 ms 2312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 3 ms 2420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 3 ms 2420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 3 ms 2420 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 3 ms 2436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 3 ms 2436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 3 ms 2436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 3 ms 2436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 3 ms 2436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 4 ms 2436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 3 ms 2448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 4 ms 2448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 3 ms 2448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 4 ms 2448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 4 ms 2448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 6 ms 2512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 4 ms 2512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 4 ms 2512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 3 ms 2512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 5 ms 2524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 5 ms 2524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 12 ms 2896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 4 ms 2896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 4 ms 2896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 4 ms 2896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 19 ms 3408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 16 ms 3484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 14 ms 3484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 21 ms 3812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 5 ms 3812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 6 ms 3812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 8 ms 3812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 10 ms 3812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Runtime error 13 ms 3812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 21 ms 3812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Runtime error 12 ms 3812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 28 ms 4432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 25 ms 4432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 24 ms 4432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 30 ms 4612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 5 ms 4612 KB Execution killed with signal 11 (could be triggered by violating memory limits)