Codeforces Round #433 (Div. 2) D. Jury Meeting

競プロ Codeforces

問題文

http://codeforces.com/contest/853/problem/B

問題概要

街が n + 1 あり，それぞれナンバリングされている．また人が n 人いて，人 i は街 i に存在する．0番目の街は首都であり，人はいない．
ここで，飛行機のスケジュールが m 個与えられる．スケジュールは以下のようになっている．
d[i] 日に出発してその日のうちに到着し，街 f[i] から 街 t[i] に行くが，これにはコストが c[i] かかる．また，f[i] == 0 または t[i] == 0 が必ず成り立つ．（どちらかは必ず首都である）
この時，n 人すべてが首都に同時に k 日間いるような期間が存在し，かつ自分の街まで帰るような飛行機の利用の仕方で，コストを最小化せよ．

・制約
1 <= n <= 10^5
0 <= m <= 10^5
1 <= k <= 10^6
1 <= d[i] <= 10^6
0 <= f[i], t[i] <= 10^6
1 <= c[i] <= 10^6

解法

最初に d[i] でスケジュールをソートしておきます．

まず，コストを無視して全員が最短で首都につくタイミングを lb，全員が自分の街まで帰ることができるギリギリを ub とします．（後者は，スケジュールを逆順に見れば良いです．）

lb と ub の日の差が k + 1 より小さければ，同時に k 日間滞在できません．
そうでない場合は，幅が k + 1 より小さくならないように，lb と ub をいい感じに伸ばしてやって，その中で一番良いものを選ぶことになります．

これはちょうどしゃくとりっぽい発想なので，それで実装します．
go[i] := i 番目の人が行きで使えるコストの集合 (multiset)
ret[i] := i 番目の人が帰りで使えるコストの集合 (multiset)
とし，伸ばすときは insert して，縮めるときは erase します．
値の更新は begin() の値を足し引きするだけなので，難しくはないです．

計算量は O(mlogm + n) ．

ソースコード

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

constexpr int INF = 1e9;
constexpr long double eps = 1e-8;

struct flight {
    int d, f, t, c;

    bool operator<(flight const& f) const {
        return d < f.d;
    }
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<flight> fs(m);
    for(int i = 0; i < m; ++i) {
        scanf("%d %d %d %d", &fs[i].d, &fs[i].f, &fs[i].t, &fs[i].c);
    }
    sort(begin(fs), end(fs));

    vector<multiset<ll>> go(n + 1), ret(n + 1);
    set<int> gs, rs;
    int lb = -1, ub = -1;
    for(int i = 0; i < m; ++i) {
        if(fs[i].t == 0) {
            go[fs[i].f].insert(fs[i].c);
            gs.insert(fs[i].f);
        }
        if(gs.size() == n) {
            lb = i;
            break;
        }
    }
    for(int i = m - 1; i >= 0; --i) {
        if(fs[i].f == 0) {
            ret[fs[i].t].insert(fs[i].c);
            rs.insert(fs[i].t);
        }
        if(rs.size() == n) {
            ub = i;
            break;
        }
    }

    if(lb == -1 || ub == -1 || fs[ub].d - fs[lb].d < k + 1) {
        cout << -1 << endl;
        return 0;
    }

    int l = lb, r = ub;
    while(fs[ub].d - fs[l + 1].d >= k + 1) {
        if(fs[l + 1].t == 0) {
            go[fs[l + 1].f].insert(fs[l + 1].c);
        }
        l++;
    }

    ll t = 0;
    for(int i = 1; i <= n; ++i) {
        t += *go[i].begin() + *ret[i].begin();
    }

    ll res = t;
    while(fs[r - 1].d - fs[lb].d >= k + 1) {
        r--;
        while(fs[r].d - fs[l].d < k + 1) {
            if(fs[l].t == 0) {
                t -= *go[fs[l].f].begin();
                go[fs[l].f].erase(fs[l].c);
                t += *go[fs[l].f].begin();
            }
            l--;
        }
        if(fs[r].f == 0) {
            t -= *ret[fs[r].t].begin();
            ret[fs[r].t].insert(fs[r].c);
            t += *ret[fs[r].t].begin();
        }
        res = min(res, t);
    }

    cout << res << endl;
}