Submission #95458

#	Time	Username	Problem	Language	Result	Execution time	Memory
95458		choikiwon	Marriage questions (IZhO14_marriage)	C++17	42 / 100	122 ms	8152 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];
int who[MN];

void con(int x) {
    V = N + M + 2, src = V - 2, snk = V - 1;
    init();
    for(int i = 0; i <= x; 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 = 0; u <= x; 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);
    }
    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;
    while(s <= e) {
        int m = (s + e)>>1;

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

    con(p);
    dinic();

    memset(who, -1, sizeof(who));
    for(int u = 0; 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 v = who[i - 1];
            while(adj[v].size() && (who[ adj[v].back() ] != -1 || adj[v].back() < i)) {
                adj[v].pop_back();
            }
            if(adj[v].size()) {
                p = max(p, adj[v].back());
                who[ adj[v].back() ] = v;
                who[v] = adj[v].back();
            }
            else break;
        }
        ans += N - p;
    }
    printf("%lld", ans);
}

Compilation message (stderr)

marriage.cpp: In function 'void con(int)':
marriage.cpp:81: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:91: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:94: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: 42 / 100