mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #335 (Div. 1) B. Lazy Student

解法

最小全域木を作るときは, 小さいコストの辺を優先して選んでいき, もしその辺を追加してもループが得られなかったら木の辺として追加する, というアルゴリズムを使いますが, この問題の基本的なアイデアはそれです。

頂点 1 にすべての頂点をつなげる形で最小全域木を作ることを考えますが, もし余計な辺を付け加えなければならなくなったら, 1 以外の頂点 v, u を使って v-u に辺をつなげます。ただし, この v と u は, すでに 1 と辺をつなげた頂点でなければなりません(そうしないと上のアルゴリズムの正当性を利用できないので)。

余計な辺(最小全域木に関係ない辺)の管理に戸惑っていたのですが, set なり vector なりで余計な辺を追加していき, 余計な辺を使う必要が出てきたらそれを辺の集合から消していけば良いだけでした…(集合のサイズは m に押さえておけば OK)

struct edge {
    int w;
    int use;
    int id;
    edge() {}
    edge(int w, int use, int id) : w(w), use(use), id(id) {}
    bool operator<(const edge& rhs) const {
        if (w != rhs.w) return w < rhs.w;
        return use > rhs.use;
    }
};

pii ans[100010];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<edge> E(m);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        E[i] = edge(a, b, i);
    }
    set<pii> P;
    sort(E.begin(), E.end());
    int rest = 0;
    for (int i = 0; i < m; i++) {
        int id = E[i].id;
        if (E[i].use) {
            ans[id].first = 1;
            ans[id].second = rest+2;
            for (int j = 2; j < rest+2; j++) {
                if (P.size() > m) break;
                P.insert(pii(j, rest+2));
            }
            rest++;
        } else {
            if (P.empty()) {
                cout << -1 << endl;
                return 0;
            } else {
                ans[id] = *P.begin();
                P.erase(P.begin());
            }
        }
    }
    for (int i = 0; i < m; i++) {
        cout << ans[i].first << " " << ans[i].second << endl;
    }
    return 0;
}