Submission #553936

#	Time	Username	Problem	Language	Result	Execution time	Memory
553936		elazarkoren	Robots (IOI13_robots)	C++17	39 / 100	119 ms	65536 KiB

robots

#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 c[MAX_N][MAX_N];
priority_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], c[a][b]);
    e[a] -= x, c[a][b] -= x;
    if (!e[b] && b != sink) {
        q.push({label[a], b});
    }
    e[b] += x, c[b][a] += x;
}

void Relabel(int a) {
    label[a] = infinity;
    for (int neighbor : graph[a]) {
        if (c[a][neighbor]) {
            chkmin(label[a], short(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 (c[a][b] && label[b] == label[a] - 1) 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.top().y;
        q.pop();
        Discharge(node);
    }
    return e[sink] == t;
}

bool Match(int time) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            c[i][j] = 0;
        }
    }
    for (int i = 0; i < t; i++) {
        for (int neighbor : graph[i]) {
            if (neighbor != source) {
                c[i][neighbor] = 1;
            }
        }
        c[source][i] = 1;
    }
    for (int i = t; i < t + a + b; i++) {
        c[i][sink] = time;
    }
    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);
                graph[j + t].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);
                graph[j + t + a].push_back(i);
            }
        }
    }
    source = t + a + b;
    sink = t + a + b + 1;
    for (int i = 0; i < t; i++) {
        graph[source].push_back(i);
        graph[i].push_back(source);
    }
    for (int i = t; 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
*/

Compilation message (stderr)

robots.cpp: In function 'void Discharge(short int)':
robots.cpp:54:20: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if (ind[a] == graph[a].size()) {
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~

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