| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 553953 | elazarkoren | Robots (IOI13_robots) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "robots.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
#define int short
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_T = 1e4 + 5;
const int MAX_A = 1000 + 5;
const int MAX_B = 1000 + 5;
const int infinity = 2e4;
int a, b, t;
const int MAX_N = 1e4 + 1e3 + 2;
int f[MAX_T][MAX_A];
int c[MAX_T][MAX_A];
queue<pii> q;
int e[MAX_N], label[MAX_N];
vi graph[MAX_N];
int ind[MAX_N];
int source, sink;
void Push(int a, int b) {
int x = min(e[a], (a < b ? c[a][b] : f[b][a] - c[b][a]));
e[a] -= x;
if (a < b) c[a][b] -= x;
else c[b][a] += x;
if (!e[b] && b != sink) {
q.push({label[a], b});
}
e[b] += x;
}
void Relabel(int a) {
label[a] = infinity;
for (int neighbor : graph[a]) {
if (a < neighbor && c[a][neighbor] > 0 || a > neighbor && c[neighbor][a] != f[neighbor][a]) {
chkmin(label[a], int(label[neighbor] + 1));
}
}
}
void Discharge(int a) {
while (e[a]) {
if (ind[a] == graph[a].size()) {
Relabel(a);
ind[a] = 0;
}
int b = graph[a][ind[a]];
if (label[b] == label[a] - 1) {
if (a < b && c[a][b] > 0 || a > b && c[b][a] != f[b][a]) {
Push(a, b);
}
}
ind[a]++;
}
}
int n;
bool MaxFlow() {
fill(e, e + n, 0);
e[source] = infinity;
for (int neighbor : graph[source]) {
Push(source, neighbor);
}
fill(label, label + n, 0);
fill(ind, ind + n, 0);
label[source] = n;
while (!q.empty()) {
int node = q.front().y;
q.pop();
Discharge(node);
}
return e[sink] == t;
}
bool Match(int time) {
for (int i = 0; i < t; i++) {
for (int j = 0; j < n - t; j++) {
f[i][j] = 0;
c[i][j] = 0;
}
}
for (int i = 0; i < t; i++) {
for (int neighbor : graph[i]) {
if (neighbor != source) {
f[i][neighbor] = 1;
c[i][neighbor] = 1;
}
}
f[i][source] = 1;
c[i][source] = 0;
}
for (int i = t + 1; i <= t + a + b; i++) {
f[sink][i] = time;
c[sink][i] = 0;
}
return MaxFlow();
}
int32_t putaway(int32_t A, int32_t B, int32_t T, int32_t x[], int32_t y[], int32_t w[], int32_t s[]) {
a = A, b = B, t = T;
n = t + a + b + 2;
for (int i = 0; i < t; i++) {
for (int j = 0; j < a; j++) {
if (w[i] < x[j]) {
graph[i].push_back(j + t + 1);
graph[j + t + 1].push_back(i);
}
}
}
for (int i = 0; i < t; i++) {
for (int j = 0; j < b; j++) {
if (s[i] < y[j]) {
graph[i].push_back(j + t + a + 1);
graph[j + t + a + 1].push_back(i);
}
}
}
source = t + a + b + 1;
sink = t;
for (int i = 0; i < t; i++) {
graph[source].push_back(i);
graph[i].push_back(source);
}
for (int i = t + 1; i <= t + a + b; i++) {
graph[sink].push_back(i);
graph[i].push_back(sink);
}
int begin = 0, end = t + 1, mid;
while (begin < end) {
mid = (begin + end) >> 1;
if (Match(mid)) {
end = mid;
} else begin = mid + 1;
}
if (end == t + 1) return -1;
return end;
}
/*
3 0 6
6 2 9
4 6
8 5
7 9
1 8
5 1
8 7
*/