oj.uz

답안 #203201

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203201 2020-02-19T19:45:30 Z MKopchev Programming Contest (POI11_pro) C++14
60 / 100
 1000 ms 65540 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,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;
    for(int i=1;i<=k;i++)
    {
        scanf("%i%i",&u,&v);
        v=v+n;
        add_edge(u,v,1,0);
    }

    for(int i=n+1;i<=n+m;i++)
        add_edge(i,sink,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

pro.cpp: In function 'int main()':
pro.cpp:115: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:106: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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 632 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 1936 KB Output is correct
2 Correct 59 ms 1932 KB Output is correct
3 Correct 7 ms 380 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 689 ms 6916 KB Output is correct
2 Correct 700 ms 6916 KB Output is correct
3 Correct 12 ms 632 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 556 ms 6916 KB Output is correct
2 Execution timed out 1085 ms 12268 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 861 ms 7280 KB Output is correct
2 Correct 716 ms 6660 KB Output is correct
3 Correct 13 ms 504 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 1936 KB Output is correct
2 Correct 28 ms 7044 KB Output is correct
3 Execution timed out 1077 ms 24960 KB Time limit exceeded

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 116 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 2064 KB Output is correct
2 Execution timed out 1071 ms 14052 KB Time limit exceeded
3 Halted 0 ms 0 KB -