Submission #95463

#	Time	Username	Problem	Language	Result	Execution time	Memory
95463		choikiwon	Marriage questions (IZhO14_marriage)	C++17	60 / 100	335 ms	23604 KiB

marriage

#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 (stderr)

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 / 100