제출 #436866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
436866		114514191	Fountain Parks (IOI21_parks)	C++17	70 / 100	1072 ms	152964 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
struct Flow {
    static constexpr int INF = 1e9;
    int n;
    struct Edge {
        int to, cap;
        Edge(int to, int cap) : to(to), cap(cap) {}
    };
    std::vector<Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<int> cur, h;
    Flow(int n) : n(n), g(n) {}
    bool bfs(int s, int t) {
        h.assign(n, -1);
        std::queue<int> que;
        h[s] = 0;
        que.push(s);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int i : g[u]) {
                auto [v, c] = e[i];
                if (c > 0 && h[v] == -1) {
                    h[v] = h[u] + 1;
                    if (v == t)
                        return true;
                    que.push(v);
                }
            }
        }
        return false;
    }
    int dfs(int u, int t, int f) {
        if (u == t)
            return f;
        int r = f;
        for (int &i = cur[u]; i < int(g[u].size()); ++i) {
            int j = g[u][i];
            auto [v, c] = e[j];
            if (c > 0 && h[v] == h[u] + 1) {
                int a = dfs(v, t, std::min(r, c));
                e[j].cap -= a;
                e[j ^ 1].cap += a;
                r -= a;
                if (r == 0)
                    return f;
            }
        }
        return f - r;
    }
    void addEdge(int u, int v, int c) {
        g[u].push_back(e.size());
        e.emplace_back(v, c);
        g[v].push_back(e.size());
        e.emplace_back(u, 0);
    }
    int maxFlow(int s, int t) {
        int ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, INF);
        }
        return ans;
    }
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n = x.size();
    std::map<std::pair<int, int>, int> id;
    for (int i = 0; i < n; i++) {
        id[{x[i], y[i]}] = i;
    }
    std::vector<bool> vis(n);
    vis[0] = true;
    std::stack<int> stk;
    stk.push(0);
    std::vector<std::pair<int, int>> edges;
    while (!stk.empty()) {
        int u = stk.top();
        stk.pop();
        for (auto move : {std::make_pair(0, -2), {-2, 0}, {0, 2}, {2, 0}}) {
            int x0 = x[u] + move.first;
            int y0 = y[u] + move.second;
            if (!id.count({x0, y0})) {
                continue;
            }
            int v = id[{x0, y0}];
            if (!vis[v]) {
                edges.emplace_back(u, v);
                vis[v] = true;
                stk.push(v);
            }
        }
    }
    if (int(edges.size()) < n - 1) {
        return 0;
    }
    std::map<std::pair<int, int>, int> id2;
    std::vector<std::pair<int, int>> matches;
    std::vector<std::pair<int, int>> pts;
    auto add = [&](int u, int x, int y) {
        if (!id2.count({x, y})) {
            id2[{x, y}] = pts.size();
            pts.emplace_back(x, y);
        }
        matches.emplace_back(u, id2[{x, y}]);
    };
    for (int i = 0; i < n - 1; i++) {
        auto [u, v] = edges[i];
        if (x[u] == x[v]) {
            add(i, x[u] - 1, (y[u] + y[v]) / 2);
            add(i, x[u] + 1, (y[u] + y[v]) / 2);
        } else {
            add(i, (x[u] + x[v]) / 2, y[u] - 1);
            add(i, (x[u] + x[v]) / 2, y[u] + 1);
        }
    }
    Flow g(n + 1 + pts.size());
    int S = n - 1, T = n + pts.size();
    for (auto [u, v] : matches) {
        g.addEdge(u, n + v, 1);
    }
    for (int i = 0; i < n - 1; i++) {
        g.addEdge(S, i, 1);
    }
    for (int i = 0; i < int(pts.size()); i++) {
        g.addEdge(n + i, T, 1);
    }
    assert(g.maxFlow(S, T) == n - 1);
    std::vector<int> U, V, A, B;
    for (int i = 0; i < int(matches.size()); i++) {
        if (!g.e[2 * i].cap) {
            auto [j, k] = matches[i];
            U.push_back(edges[j].first);
            V.push_back(edges[j].second);
            A.push_back(pts[k].first);
            B.push_back(pts[k].second);
        }
    }
    build(U, V, A, B);
    return 1;
}

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