oj.uz

Submission #95463

# Submission time Handle Problem Language Result Execution time Memory
95463 2019-02-01T11:40:13 Z choikiwon Marriage questions (IZhO14_marriage) C++17
60 / 100
 335 ms 23604 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MN = 100010;

int V, E, src, snk;
vector<int> la, nxt, oppo, capa;
void init() {
    E = 0;
    la.clear(); nxt.clear(); oppo.clear(); capa.clear();
    la = vector<int>(V, -1);
}
void add(int u, int v, int c) {
    nxt.push_back(la[u]);
    la[u] = E++;
    oppo.push_back(v);
    capa.push_back(c);
}
vector<int> dist;
queue<int> q;
bool bfs() {
    dist = vector<int>(V, -1);
    q.push(src);
    dist[src] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();

        for(int i = la[u]; i != -1; i = nxt[i]) {
            int v = oppo[i];
            if(capa[i] && dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist[snk] != -1;
}
vector<int> laa;
int dfs(int u, int f) {
    if(u == snk) return f;
    for(int i = laa[u]; i != -1; i = nxt[i]) {
        laa[u] = i;
        int v = oppo[i];
        if(capa[i] && dist[v] == dist[u] + 1) {
            if(int tmp = dfs(v, min(f, capa[i]))) {
                capa[i] -= tmp;
                capa[i ^ 1] += tmp;
                return tmp;
            }
        }
    }
    return 0;
}
int dinic() {
    int tf = 0;
    while(bfs()) {
        laa = la;
        while(int tmp = dfs(src, 1e9)) tf += tmp;
    }
    return tf;
}

int N, M, K;
vector<int> adj[MN];
unordered_map<int, int> chk[MN];
int who[MN];

void con(int l, int r) {
    V = N + M + 2, src = V - 2, snk = V - 1;
    init();
    for(int i = l; i <= r; i++) {
        add(src, i, 1);
        add(i, src, 0);
    }
    for(int i = 0; i < M; i++) {
        add(N + i, snk, 1);
        add(snk, N + i, 0);
    }
    for(int u = l; u <= r; u++) {
        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];

            add(u, v, 1);
            add(v, u, 0);
        }
    }
}

int main() {
    scanf("%d %d %d", &N, &M, &K);

    for(int i = 0; i < K; i++) {
        int a, b; scanf("%d %d", &a, &b);
        a--; b--;

        adj[a].push_back(N + b);
        adj[N + b].push_back(a);
        chk[a][N + b] = 1;
        chk[N + b][a] = 1;
    }
    for(int i = 0; i < M; i++) {
        sort(adj[N + i].begin(), adj[N + i].end());
        reverse(adj[N + i].begin(), adj[N + i].end());
    }

    int s = 0, e = N - 1, p = -1, q = -1;
    while(s <= e) {
        int m = (s + e)>>1;

        con(0, m);
        if(dinic() == M) {
            p = m;
            e = m - 1;
        }
        else s = m + 1;
    }
    if(p == -1) {
        printf("0");
        return 0;
    }

    con(0, p);
    dinic();

    s = 0, e = p;
    while(s <= e) {
        int m = (s + e)>>1;

        con(m, p);
        if(dinic() == M) {
            q = m;
            s = m + 1;
        }
        else e = m - 1;
    }
    con(q, p);
    dinic();

    memset(who, -1, sizeof(who));
    for(int u = q; u <= p; u++) {
        for(int i = la[u]; i != -1; i = nxt[i]) {
            int v = oppo[i];
            if(v != src && !capa[i]) {
                who[u] = v;
                who[v] = u;
                break;
            }
        }
    }

    ll ans = N - p;
    for(int i = 1; i < N; i++) {
        if(who[i - 1] != -1) {
            int u = who[i - 1];

            bool found = false;
            while(p + 1 < N) {
                ++p;

                bool ok = false;
                int mn = 1e9, mnp = -1;
                for(int j = 0; j < adj[p].size(); j++) {
                    int v = adj[p][j];
                    if(v == u) {
                        who[u] = p;
                        who[p] = u;
                        ok = true;
                        break;
                    }
                    int x = who[v];
                    if(chk[x][u]) {
                        who[u] = x;
                        who[x] = u;
                        who[v] = p;
                        who[p] = v;
                        ok = true;
                        break;
                    }
                    if(mn > x) {
                        mn = x;
                        mnp = v;
                    }
                }
                if(ok) {
                    found = true;
                    break;
                }
                if(mnp != -1) {
                    who[mn] = -1;
                    who[mnp] = p;
                    who[p] = mnp;
                }
            }
            if(!found) break;
        }
        ans += N - p;
    }
    printf("%lld", ans);
}

Compilation message

marriage.cpp: In function 'void con(int, int)':
marriage.cpp:82:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < adj[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~
marriage.cpp: In function 'int main()':
marriage.cpp:164:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j = 0; j < adj[p].size(); j++) {
                                ~~^~~~~~~~~~~~~~~
marriage.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &M, &K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:95:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d %d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8568 KB Output is correct
2 Incorrect 9 ms 8568 KB Output isn't correct
3 Correct 9 ms 8568 KB Output is correct
4 Correct 9 ms 8568 KB Output is correct
5 Correct 8 ms 8568 KB Output is correct
6 Correct 9 ms 8568 KB Output is correct
7 Incorrect 9 ms 8568 KB Output isn't correct
8 Correct 11 ms 8568 KB Output is correct
9 Correct 8 ms 8184 KB Output is correct
10 Correct 8 ms 8184 KB Output is correct
11 Correct 9 ms 8568 KB Output is correct
12 Correct 9 ms 8184 KB Output is correct
13 Correct 9 ms 8572 KB Output is correct
14 Incorrect 8 ms 8572 KB Output isn't correct
15 Incorrect 8 ms 8568 KB Output isn't correct
16 Correct 9 ms 8568 KB Output is correct
17 Incorrect 9 ms 8568 KB Output isn't correct
18 Incorrect 9 ms 8568 KB Output isn't correct
19 Correct 10 ms 8824 KB Output is correct
20 Incorrect 8 ms 8568 KB Output isn't correct
21 Correct 9 ms 8184 KB Output is correct
22 Correct 9 ms 8540 KB Output is correct
23 Incorrect 10 ms 8696 KB Output isn't correct
24 Incorrect 10 ms 8696 KB Output isn't correct
25 Incorrect 21 ms 9976 KB Output isn't correct
26 Incorrect 13 ms 8952 KB Output isn't correct
27 Correct 10 ms 8308 KB Output is correct
28 Correct 8 ms 8568 KB Output is correct
29 Correct 19 ms 9976 KB Output is correct
30 Correct 18 ms 9848 KB Output is correct
31 Incorrect 89 ms 14324 KB Output isn't correct
32 Incorrect 25 ms 9336 KB Output isn't correct
33 Correct 11 ms 8312 KB Output is correct
34 Correct 12 ms 8920 KB Output is correct
35 Incorrect 131 ms 20760 KB Output isn't correct
36 Incorrect 105 ms 18384 KB Output isn't correct
37 Incorrect 114 ms 15344 KB Output isn't correct
38 Correct 165 ms 21204 KB Output is correct
39 Correct 23 ms 9592 KB Output is correct
40 Correct 54 ms 10284 KB Output is correct
41 Incorrect 107 ms 11852 KB Output isn't correct
42 Correct 76 ms 13284 KB Output is correct
43 Correct 110 ms 15844 KB Output is correct
44 Correct 164 ms 21204 KB Output is correct
45 Incorrect 153 ms 14308 KB Output isn't correct
46 Incorrect 244 ms 22664 KB Output isn't correct
47 Correct 251 ms 23116 KB Output is correct
48 Correct 226 ms 22096 KB Output is correct
49 Incorrect 335 ms 23604 KB Output isn't correct
50 Correct 31 ms 10240 KB Output is correct