Submission #203202

#	Time	Username	Problem	Language	Result	Execution time	Memory
203202		MKopchev	Programming Contest (POI11_pro)	C++14	60 / 100	1092 ms	65536 KiB

pro

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e3+42,inf=2e9+42;

int n,m,r,t,k;
struct edge
{
    int from,to,flow,cost,id_back;
};
vector<edge> edges;
vector<int> adj[nmax];

void add(int from,int to,int flow,int cost)
{
    int id_back=edges.size()^1;
    edge current;
    current.from=from;
    current.to=to;
    current.flow=flow;
    current.cost=cost;
    current.id_back=id_back;

    adj[from].push_back(edges.size());
    edges.push_back(current);
}

void add_edge(int from,int to,int flow,int cost)
{
    add(from,to,flow,cost);
    add(to,from,0,-cost);
}

int id_of_edge_to_parent[nmax],dist[nmax];

int source,sink;

void bellman()
{
    for(int i=source;i<=sink;i++)id_of_edge_to_parent[i]=-1,dist[i]=inf;

    dist[source]=0;
    while(1)
    {
        bool change=0;
        for(auto k:edges)
            if(k.flow&&dist[k.from]+k.cost<dist[k.to])
            {
                change=1;
                dist[k.to]=dist[k.from]+k.cost;
                id_of_edge_to_parent[k.to]=k.id_back^1;
            }
        if(change==0)return;
    }
}

void push(int id)
{
    edges[id].flow--;
    edges[edges[id].id_back].flow++;
}
void min_cost_max_flow()
{
    long long flow=0,cost=0;
    while(1)
    {
        bellman();
        if(dist[sink]==inf)break;

        flow++;
        cost=cost+dist[sink];

        int node=sink;

        //cout<<"path: ";
        while(node!=source)
        {
            push(id_of_edge_to_parent[node]);
            node=edges[id_of_edge_to_parent[node]].from;
            //cout<<node<<" ";
        }
        //cout<<endl;
    }

    printf("%lld %lld\n",flow,cost);
    for(int i=1;i<=n;i++)
    {
        int t_now=0;
        for(auto k:adj[i])
            if(n+1<=edges[k].to&&edges[k].to<=n+m&&edges[k].flow==0)
            {
                printf("%i %i %i\n",i,edges[k].to-n,t_now);
                t_now+=r;
            }
    }
}
int main()
{
    scanf("%i%i%i%i%i",&n,&m,&r,&t,&k);

    source=0;
    sink=n+m+1;

    int u,v;

    vector< pair<int,int> > mem={};
    for(int i=1;i<=k;i++)
    {
        scanf("%i%i",&u,&v);
        v=v+n;
        mem.push_back({u,v});
    }

    for(int i=n+1;i<=n+m;i++)
        add_edge(i,sink,1,0);

    for(auto k:mem)
        add_edge(k.first,k.second,1,0);

    for(int i=1;i<=n;i++)
        for(int j=0;(j+1)*r<=t&&j<adj[i].size();j++)
            add_edge(source,i,1,(j+1)*r);

    min_cost_max_flow();
    return 0;
}

Compilation message (stderr)

pro.cpp: In function 'int main()':
pro.cpp:120:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;(j+1)*r<=t&&j<adj[i].size();j++)
                                 ~^~~~~~~~~~~~~~
pro.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i%i%i",&n,&m,&r,&t,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pro.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&u,&v);
         ~~~~~^~~~~~~~~~~~~~

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