Apartments

#include <bits/stdc++.h>


// book copy-pasta
const int N = 10e5;
std::vector<int> adj[N];
bool visited[N];
int matching[N];  // additional

// modified
bool dfs(int s) {
    visited[s] = true;

    // go through neighbors
    for (auto u: adj[s]) {
        if (visited[u]) continue;

        if (matching[u] == -1) {
            // reached a node at the end of an alternating path that ends in a free node
            matching[s] = u;
            matching[u] = s;
            return true;
        }

        if (matching[u] != s) {
            // make sure we don't revisit the same match in the DFS
            visited[u] = true;

            if (dfs(matching[u])) {
                matching[s] = u;
                matching[u] = s;
                return true;
            }
        }
    }
    return false;
}

// i.e. maximum bipartite matching
void apartments() {
    int n, m, k;
    std::cin >> n >> m >> k;

    std::vector<int> desired(n);
    for (int i = 0; i < n; i++) {
        std::cin >> desired[i];
    }

    std::vector<int> apartments(m);
    for (int i = 0; i < m; i++) {
        std::cin >> apartments[i];
    }

    // model as bipartite graph
    // - applicants as nodes on the left
    // - apartments as nodes on the right
    // - edge between applicant and apartment if apartment is ok for applicant
    for (int i = 0; i < n; i++) {
        int applicant_desired = desired[i];
        for (int j = 0; j < m; j++) {
            int apt = apartments[j];
            int apt_i = n + j;
            if (applicant_desired >= apt - k && applicant_desired <= apt + k) {
                // add both directions
                adj[i].push_back(apt_i);
                adj[apt_i].push_back(i);
            }
        }
    }

    // mark all nodes as unvisited and unmatched
    for (int i = 0; i < n * m; i++) {
        matching[i] = -1;
    }

    // algorithm itself
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (matching[i] == -1) {
            // mark everything unvisited
            for (int j = 0; j < n * m; j++) {
                visited[i] = false;
            }
            // preform dfs
            if (dfs(i)) count++;
        }
    }

    std::cout << count << std::endl;
}

int main() {
    std::basic_ostream<char, std::char_traits<char>>::sync_with_stdio(false);
    std::cin.exceptions(std::istream::failbit);

    apartments();

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: TIME LIMIT EXCEEDED

Test 15

Verdict: TIME LIMIT EXCEEDED

Test 16

Verdict: TIME LIMIT EXCEEDED

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED