Submission #203218

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
203218	2020-02-19T20:23:03 Z	MKopchev	Programming Contest (POI11_pro)	C++14	100 / 100	194 ms	13920 KB

#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,id_back;
};
vector<edge> edges;
vector<int> adj[nmax];

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

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

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

int source,sink;

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

int cost_start[nmax];

void push(int id)
{
    //cout<<"push "<<id<<" "<<edges[id].from<<" "<<edges[id].to<<endl;

    edges[id].flow--;
    edges[edges[id].id_back].flow++;
}
bool been[nmax];

bool dfs(int node)
{
    if(node==sink)return 1;
    if(been[node])return 0;
    been[node]=1;
    for(auto k:adj[node])
        if(edges[k].flow)
        {
            if(dfs(edges[k].to))
            {
                push(k);
                return 1;
            }
        }
    return 0;
}
void min_cost_max_flow()
{
    long long flow=0,cost=0;
    while(1)
    {
        memset(been,0,sizeof(been));

        vector< pair<int/*dist_now*/,int/*start*/> > possible={};
        for(int i=1;i<=n;i++)
            if(cost_start[i]<=t)possible.push_back({cost_start[i],i});

        sort(possible.begin(),possible.end());

        bool path=0;
        for(auto current:possible)
        {
            if(dfs(current.second))
            {
                flow++;
                cost+=current.first;
                cost_start[current.second]+=r;
                path=1;
                break;
            }
        }
        if(path==0)break;
    }
    /*
    for(auto k:edges)
        if(k.flow==0)cout<<k.from<<" "<<k.to<<" "<<k.flow<<" "<<k.id_back<<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);

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

    for(int i=1;i<=n;i++)
        cost_start[i]=r;

    min_cost_max_flow();
    return 0;
}

Compilation message

pro.cpp: In function 'int main()':
pro.cpp:108: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:118: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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	376 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	632 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	1776 KB	Output is correct
2	Correct	17 ms	1264 KB	Output is correct
3	Correct	6 ms	380 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	6244 KB	Output is correct
2	Correct	114 ms	6248 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	6080 KB	Output is correct
2	Correct	76 ms	2096 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	135 ms	7400 KB	Output is correct
2	Correct	58 ms	3692 KB	Output is correct
3	Correct	6 ms	376 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	1904 KB	Output is correct
2	Correct	27 ms	6632 KB	Output is correct
3	Correct	113 ms	7140 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	6756 KB	Output is correct
2	Correct	5 ms	388 KB	Output is correct
3	Correct	6 ms	428 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	2032 KB	Output is correct
2	Correct	194 ms	13920 KB	Output is correct
3	Correct	10 ms	552 KB	Output is correct