제출 #298425

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
298425		Haunted_Cpp	로봇 (IOI13_robots)	C++17	39 / 100	249 ms	65540 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

struct FlowEdge {
  int u, v;
  long long cap, flow = 0;
  FlowEdge (int from, int to, long long w) : u (from), v (to), cap (w) {}
};
 
struct EdmondsKarp {
  const long long flow_inf = 1e18;
  vector<FlowEdge> edge;
  vector< vector<int> > g;
  vector<int> parent;
  int m, source, sink;
  EdmondsKarp (int n, int s, int t) : m(0), source (s), sink (t) {
    edge.clear();
    g.clear(); g.resize(n);
    parent.clear(); parent.resize(n);
  }
  void addEdge (int u, int v, long long w) {
    edge.emplace_back(u, v, w);
    edge.emplace_back(v, u, 0);
    g[u].emplace_back(m);
    g[v].emplace_back(m + 1);
    m += 2;
  }
  long long bfs () {
    fill (parent.begin(), parent.end(), -1);
    queue<pair<int, long long > > q;
    q.push({source, flow_inf});
    while (!q.empty()) {
      int node = q.front().first;
      long long mn = q.front().second;
      q.pop();
      if (node == sink) return mn;
      if (mn == 0) return 0;
      for (auto to : g[node]) {
        if (parent[edge[to].v] == -1 && edge[to].cap - edge[to].flow >= 1) {
          parent[edge[to].v] = to;
          q.push({edge[to].v, min (mn, edge[to].cap - edge[to].flow)});
        }
      }
    }
    return 0;
  }
  long long flow () {
    long long f = 0;
    while (long long add = bfs ()) {
      f += add;
      int cur = sink;
      while (cur != source) {
        int node = parent[cur];
        edge[node].flow += add;
        edge[node ^ 1].flow -= add;
        cur = edge[parent[cur]].u;
      }
    }
    return f;
  }
};

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
  vector<int> weak, small;
  for (int i = 0; i < A; i++) {
    weak.emplace_back(X[i]);
  }  
  for (int i = 0; i < B; i++) {
    small.emplace_back(Y[i]);
  }
  vector<pair<int, int>> arr(T);
  for (int i = 0; i < T; i++) {
    arr[i] = {W[i], S[i]};
  }
  sort(weak.begin(), weak.end());
  sort(small.begin(), small.end());
  // SHOULD WORK FOR T <= 10_000 ? 
  auto works = [&](int time) {
    EdmondsKarp solve(2 * T + 2 * A + 2 * B + 10, 0, 1);
    int cur = 2;
    for (int i = 0; i < A; i++) {
      solve.addEdge(0, cur, time);
      for (int j = 0; j < T; j++) {
        if (arr[j].first < X[i]) {
          solve.addEdge(cur, A + B + 5 + j, 1); 
        }
      }
      ++cur;
    }
    for (int i = 0; i < B; i++) {
      solve.addEdge(0, cur, time);
      for (int j = 0; j < T; j++) {
        if (arr[j].second < Y[i]) {
          solve.addEdge(cur, A + B + 5 + j, 1); 
        }
      }
      ++cur;
    }
    for (int j = 0; j < T; j++) {
      solve.addEdge(A + B + 5 + j, 1, 1); 
    }
    return (solve.flow() == T);
  };
  int lo = 0, hi = 1e9;
  while(lo < hi) {
    const int mid = lo + (hi - lo) / 2;
    if (works(mid)) hi = mid;
    else lo = mid + 1;
  }
  return (hi > 1e8 ? -1 : hi);
}

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