Submission #1240894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240894		trimkus	Fountain Parks (IOI21_parks)	C++20	55 / 100	1196 ms	103632 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

struct DSU {
    vector<int> e;
    DSU (int n) {
        e = vector<int>(n, -1);
    }
    int get(int x) {
        return e[x] < 0 ? x : e[x] = get(e[x]);
    }
    int size(int x) {
        return -e[get(x)];
    }
    bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y];
        e[y] = x;
        return true;
    }
};

vector<vector<int>> adj;
vector<int> matched_to;
int idx;
bool try_kuhn(int v, vector<bool> &visited, vector<int> &matched_to) {
    if (visited.at(v)) return false;
    visited.at(v) = true;
    
    for (int to : adj.at(v)) {
        if (matched_to.at(to) == -1 || try_kuhn(matched_to.at(to), visited, matched_to)) {
            matched_to.at(to) = v;
            return true;
        }
    }
    return false;
}

int bipartite_matching(int n) {
    int matches = 0;
    for (int i = idx; i < n; i++) {
        vector<bool> visited = vector<bool>(n, false);
        if (try_kuhn(i, visited, matched_to)) {
            matches += 1;
        }
    }
    return matches;
}

void add_edge(int i, int j) {
    adj[i].push_back(j);
}


int construct_roads(std::vector<int> x, std::vector<int> y) {
    int N = x.size();
    const int MAXN = 2e5;
    vector<map<int, int>> mp(MAXN + 10);
    for (int i = 0; i < N; ++i) {
        mp[x[i]][y[i]] = i;
    }
    idx = N;
    vector<map<int, int>> pl(MAXN + 10);
    vector<array<int, 2>> rev;
    vector<int> dx = {1, 1, -1, -1}, dy = {1, -1, 1, -1};
    vector<array<int, 2>> edges;
    for (int i = 0; i < N; ++i) {
        for (int k = 0; k < 4; ++k) {
            int nx = x[i] + dx[k];
            int ny = y[i] + dy[k];
            if (!pl[nx].count(ny)) {
                pl[nx][ny] = idx++;
                rev.push_back({nx, ny});
            }
        }
    }
    DSU dsu(N);
    for (int i = 0; i < N; ++i) {
        if (mp[x[i]].count(y[i] + 2)) {
            dsu.unite(i, mp[x[i]][y[i] + 2]);
            edges.push_back({i, mp[x[i]][y[i] + 2]});
        }
        if (mp[x[i] + 2].count(y[i])) {
            dsu.unite(i, mp[x[i] + 2][y[i]]);
            edges.push_back({i, mp[x[i] + 2][y[i]]});
        }
    }
    if (dsu.size(0) != N) return 0;
    adj.resize(edges.size() + idx + 1);
    matched_to = vector<int>(edges.size() + idx + 1, -1);
    for (int it = 0; it < edges.size(); ++it) {
        int i = edges[it][0];
        int j = edges[it][1];
        if (x[i] == x[j]) {
            int ny = y[i] + 1;
            int nx = x[i] + 1;
            assert(pl[nx].count(ny));
            int index = pl[nx][ny];
            add_edge(it + idx, index);
            nx = x[i] - 1;
            assert(pl[nx].count(ny));
            index = pl[nx][ny];
            add_edge(it + idx, index);
        } else {
            assert(y[i] == y[j]);
            int ny = y[i] + 1;
            int nx = x[i] + 1;
            assert(pl[nx].count(ny));
            int index = pl[nx][ny];
            add_edge(it + idx, index);
            ny = y[i] - 1;
            assert(pl[nx].count(ny));
            index = pl[nx][ny];
            add_edge(it + idx, index);
        }
    }
    // cout << N << "\n";
    // for (int it = 0; it < idx + edges.size(); ++it) {
    //     cout << it << ": ";
    //     for (auto& u : adj[it]) {
    //         cout << u << " ";
    //     }
    //     cout << "\n";
    // }
    // cerr << endl;
    int matches = bipartite_matching(edges.size() + idx + 1);
    assert(matches == (int)edges.size());
    vector<int> u, v, a, b;
    for (int it = N; it < idx; ++it) {
        // cout << matched_to[it] << " ";
        if (matched_to[it] == -1) continue;
        int i = edges[matched_to[it] - idx][0];
        int j = edges[matched_to[it] - idx][1];
        int nx = rev[it - N][0];
        int ny = rev[it - N][1];
        u.push_back(i);
        v.push_back(j);
        a.push_back(nx);
        b.push_back(ny);
    }
    // cout << "\n";
    // for (int it = 0; it < edges.size(); ++it) {
    //     int I = it + idx;
    //     int J = matched_to[I];
    //     assert(J != -1);
    // }
    build(u, v, a, b);
    return 1;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30