Submission #65332

#	Time	Username	Problem	Language	Result	Execution time	Memory
65332		edisonhello	Robots (IOI13_robots)	C++14	0 / 100	4 ms	1020 KiB

robots

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

using namespace std;

struct edge{
    int u,v,f;
};
vector<edge> edg;
vector<int> G[11115];

void ae(int u,int v,int f){
    // cout<<"addedge: "<<u<<" "<<v<<" "<<f<<endl;
    G[u].push_back(edg.size());
    edg.push_back({u,v,f});
    G[v].push_back(edg.size());
    edg.push_back({v,u,0});
}

int idx[11115],vis[11115],dep[11115];

bool bfs(int s,int t,int z){
    vis[s]=z; dep[s]=1;
    queue<int> q; q.push(s);
    while(q.size()){
        int now=q.front(); q.pop();
        for(int eid:G[now]){
            edge &e=edg[eid];
            if(vis[e.v]!=z && e.f>0){
                q.push(e.v);
                vis[e.v]=z;
                dep[e.v]=dep[now]+1;
            }
        }
    }
    // cout<<"finish bfs"<<endl;
    return (vis[t]==z);
}

int dfs(int now,int fl,int dis){
    if(now==dis)return fl;
    if(!fl)return 0;
    int rt=0;
    for(int &i=idx[now];i<G[now].size();++i){
        int eid=G[now][i];
        edge &e=edg[eid];
        if(dep[e.v]==dep[now]+1 && e.f>0){
            int f=dfs(e.v,min(fl,e.f),dis);
            rt+=f; fl-=f;
            e.f-=f;
            edg[eid^1].f+=f;
            if(!fl)return rt;
        }
    }
    return rt;
}

int flow(int s,int t){
    int vis_ptr=0,ans=0;
    while(bfs(s,t,++vis_ptr)){
        memset(idx,0,sizeof(idx));
        ans+=dfs(s,1e9,t);
    }
    return ans;
}

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
    // cout<<"in: putaway"<<endl;
    for(int i=0;i<a;++i){
        for(int j=0;j<t;++j){
            if(w[j]<=x[i])ae(t+i,j,1);
        }
    }
    for(int i=0;i<b;++i){
        for(int j=0;j<t;++j){
            if(s[j]<=y[i])ae(t+a+i,j,1);
        }
    }
    for(int i=0;i<t;++i)if(G[i].empty())return -1;
    for(int i=0;i<t;++i)ae(i,11114,1);
    int f=0;
    for(int T=1;;++T){
        for(int i=0;i<a;++i)ae(11113,t+i,1);
        for(int i=0;i<b;++i)ae(11113,t+a+i,1);
        f+=flow(11113,11114);
        if(f==t)return T;
    }
}

Compilation message (stderr)

robots.cpp: In function 'int dfs(int, int, int)':
robots.cpp:44:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int &i=idx[now];i<G[now].size();++i){
                         ~^~~~~~~~~~~~~~

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