Submission #1101387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101387		alexander707070	Robots (IOI13_robots)	C++14	39 / 100	94 ms	20676 KiB

robots

#include<bits/stdc++.h>
#include "robots.h"

#define MAXN 10007
using namespace std;

struct edge{
    int to,flow,cap,rev;
};

int n,m,k;
int x[MAXN],y[MAXN];
pair<int,int> s[MAXN],t[MAXN];

bool cmp(pair<int,int> fr,pair<int,int> sc){
    return fr.second<sc.second;
}

int cnt[MAXN],cnt2[MAXN];
vector<edge> g[MAXN];

void add_edge(int from,int to){
    g[from].push_back({to,0,1,int(g[to].size())});
    g[to].push_back({from,0,0,int(g[from].size())-1});
}

int source,sink,flow,maxflow;
int li[MAXN],tim;

int dfs(int x){
    if(x==sink)return 1;

    li[x]=tim;
    for(int i=0;i<g[x].size();i++){
        if(li[g[x][i].to]==tim or g[x][i].cap-g[x][i].flow==0)continue;

        int curr=dfs(g[x][i].to);
        if(curr>0){
            g[x][i].flow++;
            g[g[x][i].to][g[x][i].rev].flow--;
            return 1;
        }
    }

    return 0;
}

bool check(int days){

    source=0; sink=(n+m)*days+k+1;
    for(int i=0;i<=sink;i++)g[i].clear();

    for(int i=1;i<=(n+m)*days;i++)add_edge(source,i);
    for(int i=1;i<=k;i++)add_edge((n+m)*days+i,sink);

    for(int i=1;i<=n;i++){
        for(int f=1;f<=k and x[i]>s[f].first;f++){
            for(int t=1;t<=days;t++){
                add_edge((i-1)*days+t,(n+m)*days+f);
            }
        }
    }

    for(int i=1;i<=m;i++){
        for(int f=1;f<=k;f++){
            if(y[i]<=s[f].second)continue;

            for(int t=1;t<=days;t++){
                add_edge(n*days+(i-1)*days+t,(n+m)*days+f);
            }
        }
    }

    maxflow=0;
    while(true){
        tim++;
        flow=dfs(source);

        if(flow==0)break;
        maxflow+=flow;
    }

    return maxflow==k;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
//int putaway(int A, int B, int T, vector<int> X, vector<int> Y, vector<int> W, vector<int> S) {
    n=A; m=B; k=T;

    for(int i=1;i<=n;i++)x[i]=X[i-1];
    for(int i=1;i<=m;i++)y[i]=Y[i-1];
    for(int i=1;i<=k;i++)s[i]=t[i]={W[i-1],S[i-1]};

    sort(x+1,x+n+1);
    sort(y+1,y+m+1);

    sort(s+1,s+k+1);
    sort(t+1,t+k+1,cmp);

    if(x[n]<=s[k].first and y[m]<=s[k].second)return -1;

    int l=0,r=k+1,tt;
    while(l+1<r){
        tt=(l+r)/2;

        if(check(tt))r=tt;
        else l=tt;
    }

    return r;
}


/*int main(){

    cout<<putaway(3,2,10,{6,2,9},{4,7},{4,8,2,7,1,5,3,8,7,10},{6,5,3,9,8,1,3,7,6,5})<<"\n";

	return 0;
}*/

Compilation message (stderr)

robots.cpp: In function 'int dfs(int)':
robots.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<g[x].size();i++){
      |                 ~^~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10