Submission #1136052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136052		MateiKing80	Programming Contest (POI11_pro)	C++20	40 / 100	1095 ms	10676 KiB

pro

#include <bits/stdc++.h>

using namespace std;

int nn, mm, r;

struct Dinic
{
    int n;
    const int inf = 1e9;
    struct Edge
    {
        int from, to, cost, cap, prec;
    };
    vector<Edge> edge;
    vector<int> dist, h, prec, vine;
    Dinic(int N)
    {
        n = N + 5;
        dist.resize(n, inf);
        vine.resize(n);
        h.resize(n, inf);
        prec.resize(n, -1);
    }
    void baga(int from, int to, int cap, int cost)
    {
        edge.push_back({from, to, cost, cap, prec[from]});
        prec[from] = edge.size() - 1;

        edge.push_back({to, from, -cost, 0, prec[to]});
        prec[to] = edge.size() - 1;
    }
    bool bellman(int s, int d)
    {
        dist[s] = 0;
        while(1)
        {
            bool steag = 0;
            for(int j = 0; j < edge.size(); j ++)
                if(edge[j].cap > 0 && dist[edge[j].from] + edge[j].cost < dist[edge[j].to])
                {
                    dist[edge[j].to] = dist[edge[j].from] + edge[j].cost;
                    vine[edge[j].to] = j;
                    steag = 1;
                }
            if(!steag)
                break;
        }
        h = dist;
        return h[d] != inf;
    }
    bool dijkstra(int s, int d)
    {
        dist.assign(n, inf);
        vector<bool> f(n, false);
        dist[s] = 0;
        vector<int> real(n, inf);
        priority_queue<pair<int, pair<int, int>>> pq;
        pq.push({0, {s, -1}});
        real[s] = 0;
        while(!pq.empty())
        {
            auto x = pq.top();
            pq.pop();
            int g = x.second.first;
            if(f[g])
                continue;
            vine[g] = x.second.second;
            f[g] = true;
            dist[g] = -x.first;
            for(int i = prec[g]; i != -1; i = edge[i].prec)
                if(edge[i].cap > 0 && real[edge[i].to] > real[g] + edge[i].cost)
                {
                    real[edge[i].to] = real[g] + edge[i].cost;
                    pq.push({-(dist[g] + edge[i].cost - h[edge[i].to] + h[g]), {edge[i].to, i}});
                }
        }
        h = real;
        return dist[d] != inf;
    }
    pair<int, int> push(int s, int d)
    {
        pair<int, int> p;
        int x = d, minn = inf;
        while(x != s)
        {
            minn = min(minn, edge[vine[x]].cap);
            x = edge[vine[x]].from;
        }
        p.first = minn;
        x = d;
        while(x != s)
        {
            p.second += edge[vine[x]].cost * minn;
            edge[vine[x]].cap -= minn;
            edge[vine[x] ^ 1].cap += minn;
            x = edge[vine[x]].from;
        }
        return p;
    }
    pair<int, int> fmcm(int s, int d)
    {
        int flux = 0, cost = 0;
        if(!bellman(s, d))
            return {0, 0};
        while(dijkstra(s, d))
        {
            pair<int, int> p = push(s, d);
            flux += p.first;
            cost += p.second;
        }
        cout << flux << " " << cost << '\n';
        vector<int> f(nn);
        for(auto i : edge)
        {
            if(i.from < nn && i.to < mm + nn && i.cap == 0)
                cout << i.from + 1 << " " << i.to - nn + 1 << " " << (f[i.from] ++) * r << '\n';
        }
        return {flux, cost};
    }
};


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t, k;
    cin >> nn >> mm >> r >> t >> k;
    Dinic ds(nn + mm + 2);
    vector<int> f(nn);
    for(int i = 0; i < k; i ++)
    {
        int u, v;
        cin >> u >> v;
        u --, v --;
        f[u] ++;
        ds.baga(u, v + nn, 1, 0);
    }
    for(int i = 0; i < mm; i ++)
        ds.baga(i + nn, nn + mm + 1, 1, 0);
    for(int i = 0; i < nn; i ++)
        for(int j = 1; j <= min(f[i], t / r); j ++)
            ds.baga(nn + mm, i, 1, j * r);
    ds.fmcm(nn + mm, nn + mm + 1);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10