AtCoder Beginner Contest 040 D - 道路の老朽化対策について

,

http://abc040.contest.atcoder.jp/tasks/abc040_d

solution

時間でsortして順に処理。union-find木。$O(Q + M)$.

作られた時間が新しい順に、辺を追加していく。 ある人が到達できる頂点の数は、その人の家からその人の許容できる辺で繋がれた連結成分の大きさの数である。 追加する辺と質問である人を、まとめてそれらの時間でsortして、これをやればよい。

implementation

本番はIPSCのため見送った。その際unionって聞こえてきた覚えがあったから(直和構造の意味の)unionを使ってみたが、よく考えたらunion-find木のことだったのかもしれない。

また、すごく遅くてTLEぎりぎりである。なぜなのか。

#include <iostream>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
using namespace std;

struct union_find {
    vector<int> tree;
    explicit union_find(size_t n) : tree(n, -1) {}
    bool is_root(int a) { return tree[a] < 0; }
    int find_root(int a) { return is_root(a) ? a : (tree[a] = find_root(tree[a])); }
    int tree_size(int a) { return - tree[find_root(a)]; }
    void union_tree(int a, int b) {
        a = find_root(a); b = find_root(b);
        if (a != b) {
            if (not (tree_size(a) < tree_size(b))) swap(a,b);
            tree[b] += tree[a];
            tree[a] = b;
        }
    }
    bool is_connected(int a, int b) { return find_root(a) == find_root(b); }
};

const int edge_tag = 0;
const int query_tag = 1;
struct edge_t  { int tag; int y, a, b; };
struct query_t { int tag; int w, i, v; };
union event_t {
    int tag;
    struct { int tag; int time; } common;
    struct edge_t edge;
    struct query_t query;
};
bool operator < (event_t a, event_t b) {
    return make_pair(a.common.time, a.common.tag)
         > make_pair(b.common.time, b.common.tag);
}
int main() {
    // read edges
    int n, m; cin >> n >> m;
    vector<event_t> que(m);
    repeat (i,m) {
        que[i].tag = edge_tag;
        edge_t & e = que[i].edge;
        cin >> e.a >> e.b >> e.y;
        -- e.a; -- e.b;
    }
    // read queries
    int q; cin >> q;
    que.resize(m + q);
    repeat (i,q) {
        que[m+i].tag = query_tag;
        query_t & q = que[m+i].query;
        q.i = i;
        cin >> q.v >> q.w;
        -- q.v;
    }
    // compute
    whole(sort, que);
    vector<int> ans(q);
    union_find t(n);
    for (event_t e : que) {
        if (e.tag == edge_tag) {
            t.union_tree(e.edge.a, e.edge.b);
        } else if (e.tag == query_tag) {
            ans[e.query.i] = t.tree_size(e.query.v);
        }
    }
    // output
    repeat (i,q) cout << ans[i] << endl;
    return 0;
}