Submission #1124934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124934		seiryuu	Schools (IZhO13_school)	C++20	35 / 100	2098 ms	86928 KiB

school

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e18;

inline int readInt(){ char c; while (c = getchar(), c != '-' && (c < '0' || c > '9'));
    bool sign = (c == '-'); if (sign) c = getchar(); int n = c - '0';
        while(c = getchar(), c >= '0' && c <= '9') n = 10 * n + c - '0'; return ( (!sign) ? n : -n ) ; }

struct Edge {
    int to, rev;
    ll cap, cost;
};

void add_edge(vector<vector<Edge>> &g, int u, int v, ll cap, ll cost) {
    Edge a = {v, (int)g[v].size(), cap, cost};
    Edge b = {u, (int)g[u].size(), 0, -cost};
    g[u].push_back(a);
    g[v].push_back(b);
}

pair<ll, ll> min_cost_max_flow(vector<vector<Edge>> &g, int src, int snk) {
    int n = g.size();
    ll flow = 0, cost = 0;
    vector<ll> pot(n, 0);

    while (true) {
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
        vector<ll> dist(n, INF);
        vector<int> pv(n, -1), pe(n, -1);

        dist[src] = 0;
        pq.emplace(0, src);

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u]) continue;
            for (int i = 0; i < g[u].size(); i++) {
                Edge &e = g[u][i];
                if (e.cap > 0 && dist[e.to] > dist[u] + e.cost + pot[u] - pot[e.to]) {
                    dist[e.to] = dist[u] + e.cost + pot[u] - pot[e.to];
                    pv[e.to] = u;
                    pe[e.to] = i;
                    pq.emplace(dist[e.to], e.to);
                }
            }
        }

        if (dist[snk] == INF) break;

        for (int i = 0; i < n; i++) if (dist[i] < INF) pot[i] += dist[i];

        ll add_flow = INF;
        for (int v = snk; v != src; v = pv[v]) {
            int u = pv[v], idx = pe[v];
            add_flow = min(add_flow, g[u][idx].cap);
        }

        flow += add_flow;
        cost += add_flow * pot[snk];
        for (int v = snk; v != src; v = pv[v]) {
            int u = pv[v], idx = pe[v];
            g[u][idx].cap -= add_flow;
            g[v][g[u][idx].rev].cap += add_flow;
        }
    }

    return {flow, cost};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, s;
    n = readInt(), m = readInt(), s = readInt();

    int src = 0, mus = 1, spr = 2, snk = 3 + n, total = 4 + n;
    vector<vector<Edge>> g(total);

    vector<pair<int, int>> c(n);
    for (int i = 0; i < n; i++){
        c[i].first = readInt();
        c[i].second = readInt();
    }

    add_edge(g, src, mus, m, 0);
    add_edge(g, src, spr, s, 0);

    for (int i = 0; i < n; i++) {
        int city = 3 + i;
        add_edge(g, mus, city, 1, -(ll)c[i].first);
        add_edge(g, spr, city, 1, -(ll)c[i].second);
    }

    for (int i = 0; i < n; i++) {
        int city = 3 + i;
        add_edge(g, city, snk, 1, 0);
    }

    auto res = min_cost_max_flow(g, src, snk);

    if (res.first != (ll)(m + s)) {
        cout << "0";
        return 0;
    }

    cout << -res.second;
}

• Subtask 1: 35 / 100