oj.uz

Submission #90671

# Submission time Handle Problem Language Result Execution time Memory
90671 2018-12-23T12:28:50 Z popovicirobert Marriage questions (IZhO14_marriage) C++14
72 / 100
 1500 ms 23556 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 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 2 ms 1152 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 2 ms 1176 KB Output is correct
7 Correct 3 ms 1256 KB Output is correct
8 Correct 2 ms 1256 KB Output is correct
9 Correct 2 ms 1256 KB Output is correct
10 Correct 2 ms 1256 KB Output is correct
11 Correct 2 ms 1256 KB Output is correct
12 Correct 2 ms 1388 KB Output is correct
13 Correct 2 ms 1388 KB Output is correct
14 Correct 2 ms 1388 KB Output is correct
15 Correct 2 ms 1388 KB Output is correct
16 Correct 2 ms 1388 KB Output is correct
17 Correct 2 ms 1392 KB Output is correct
18 Correct 3 ms 1452 KB Output is correct
19 Correct 8 ms 1820 KB Output is correct
20 Correct 4 ms 1820 KB Output is correct
21 Correct 3 ms 1820 KB Output is correct
22 Correct 3 ms 1820 KB Output is correct
23 Correct 4 ms 1820 KB Output is correct
24 Correct 4 ms 1820 KB Output is correct
25 Correct 81 ms 3860 KB Output is correct
26 Correct 33 ms 3860 KB Output is correct
27 Correct 19 ms 3860 KB Output is correct
28 Correct 10 ms 3860 KB Output is correct
29 Correct 95 ms 3860 KB Output is correct
30 Correct 83 ms 3860 KB Output is correct
31 Correct 509 ms 10964 KB Output is correct
32 Correct 223 ms 10964 KB Output is correct
33 Correct 50 ms 10964 KB Output is correct
34 Correct 43 ms 10964 KB Output is correct
35 Correct 683 ms 20208 KB Output is correct
36 Correct 578 ms 20208 KB Output is correct
37 Execution timed out 1564 ms 20208 KB Time limit exceeded
38 Execution timed out 1570 ms 23556 KB Time limit exceeded
39 Execution timed out 1569 ms 23556 KB Time limit exceeded
40 Execution timed out 1569 ms 23556 KB Time limit exceeded
41 Execution timed out 1573 ms 23556 KB Time limit exceeded
42 Execution timed out 1574 ms 23556 KB Time limit exceeded
43 Execution timed out 1572 ms 23556 KB Time limit exceeded
44 Execution timed out 1575 ms 23556 KB Time limit exceeded
45 Execution timed out 1579 ms 23556 KB Time limit exceeded
46 Execution timed out 1577 ms 23556 KB Time limit exceeded
47 Execution timed out 1587 ms 23556 KB Time limit exceeded
48 Execution timed out 1577 ms 23556 KB Time limit exceeded
49 Execution timed out 1583 ms 23556 KB Time limit exceeded
50 Execution timed out 1586 ms 23556 KB Time limit exceeded