AOJ 1361 Deadlock Detection

解法

求めるものは unavoidable になる境界なので二分探索できそうです.
ある時刻からデットロックを避ける最良の方法は,当然 terminate できるプロセスを順に殺していくことです.
愚直にやると殺せるプロセスを探索するのに O(p^2r) かかりそうですが,あらかじめリソースごとに必要な数でソートしておくと O(prlog(p)) でできるようになります.
計算量はトータル O( (t + prlogp)logt) になります.

ソースコード

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

using pii = pair<int, int>;

int main() {
    int p, r, t;
    cin >> p >> r >> t;
    vector<int> l(r);
    vector<vector<int>> n(p, vector<int>(r));
    vector<int> P(t), R(t);
    for(int i = 0; i < r; ++i) {
        cin >> l[i];
    }
    for(int i = 0; i < p; ++i) {
        for(int j = 0; j < r; ++j) {
            cin >> n[i][j];
        }
    }
    for(int i = 0; i < t; ++i) {
        cin >> P[i] >> R[i];
        P[i]--; R[i]--;
    }

    int lb = 0, ub = t + 1;
    while(ub - lb > 1) {
        int m = (lb + ub) / 2;
        vector<int> available = l;
        vector<vector<pii>> need_r(r, vector<pii>(p));
        vector<vector<int>> used_r(p, vector<int>(r));
        vector<int> pos(r), cnt(p);
        queue<int> term_process;
        for(int i = 0; i < r; ++i) {
            for(int j = 0; j < p; ++j) {
                need_r[i][j] = make_pair(n[j][i], j);
            }
        }
        for(int i = 0; i < m; ++i) {
            available[R[i]]--;
            need_r[R[i]][P[i]].first--;
            used_r[P[i]][R[i]]++;
        }
        for(int i = 0; i < r; ++i) {
            sort(begin(need_r[i]), end(need_r[i]));
        }
        for(int i = 0; i < r; ++i) {
            while(pos[i] < p && (need_r[i][pos[i]].first == 0 || available[i] >= need_r[i][pos[i]].first)) {
                int process_id = need_r[i][pos[i]].second;
                if(++cnt[process_id] == r) {
                    term_process.push(process_id);
                }
                pos[i]++;
            }
        }
        while(!term_process.empty()) {
            int idx = term_process.front();
            term_process.pop();
            for(int i = 0; i < r; ++i) {
                available[i] += used_r[idx][i];
                while(pos[i] < p && available[i] >= need_r[i][pos[i]].first) {
                    int process_id = need_r[i][pos[i]].second;
                    if(++cnt[process_id] == r) {
                        term_process.push(process_id);
                    }
                    pos[i]++;
                }
            }
        }
        if(count(begin(cnt), end(cnt), r) == p) {
            lb = m;
        } else {
            ub = m;
        }
    }
    if(ub == t + 1) {
        cout << -1 << endl;
    } else {
        cout << ub << endl;
    }
}

感想

やるだけなんですがバグってしまった.