Submission #203209

#	Time	Username	Problem	Language	Result	Execution time	Memory
203209		MKopchev	Programming Contest (POI11_pro)	C++14	60 / 100	1097 ms	65540 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;

int type[nmax];//0-> solved, 1-> solving, 2-> to be discovered

deque<int> active;
void spfa()
{
    for(int i=source;i<=sink;i++)id_of_edge_to_parent[i]=-1,dist[i]=inf,type[i]=2;

    dist[source]=0;
    type[source]=1;
    active.push_back(source);

    while(active.size())
    {
        int current=active.front();
        active.pop_front();

        type[current]=0;
        for(auto k:adj[current])
        {
        //cout<<edges[k].from<<" "<<edges[k].cost<<" "<<edges[k].to<<endl;
            if(edges[k].flow&&dist[edges[k].from]+edges[k].cost<dist[edges[k].to])
            {
                dist[edges[k].to]=dist[edges[k].from]+edges[k].cost;
                id_of_edge_to_parent[edges[k].to]=edges[k].id_back^1;

                if(type[edges[k].to]==2)active.push_back(edges[k].to);
                else if(type[edges[k].to]==0)active.push_back(edges[k].to);

                type[edges[k].to]=1;
            }
        }
    }

    //for(int i=source;i<=sink;i++)cout<<i<<" -> "<<id_of_edge_to_parent[i]<<" "<<dist[i]<<" "<<type[i]<<endl;
}

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)
    {
        spfa();
        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:137: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:115: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:125: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