uwiさんの提出を参考に定数倍高速化したら通った。

problem

単純グラフが与えられる。その各辺には$0, \dots, m-1$という番号が付いている。 各クエリについて、区間$[l,r]$が与えられる。 この区間以外の辺を消去する。 そうしてできたグラフに関して、頂点を$2$つに分割する。 特に、残っている辺で同じ組の頂点同士を結ぶものの重みの最大値を最小化するように分割をし、そのような重みの最大値を答えよ。

solution

Use union-find tree. $O(mq\alpha(n))$.

Sort the available edges with the weight, then add them into the graph until it makes an odd-length cycle. When an odd-length cycle was made, the last edge’s weight is the answer.

The detection of the cycle can be done like the problem A of this problem set.

implementation

#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 disjoint_sets {
    vector<int> data;
    explicit disjoint_sets(size_t n) : data(n, -1) {}
    bool is_root(int a) { return data[a] < 0; }
    int find_root(int a) { return is_root(a) ? a : (data[a] = find_root(data[a])); }
    int set_size(int a) { return - data[find_root(a)]; }
    void union_sets(int a, int b) {
        a = find_root(a); b = find_root(b);
        if (a != b) {
            if (set_size(a) > set_size(b)) swap(a,b);
            data[b] += data[a];
            data[a] = b;
        }
    }
    bool is_same(int a, int b) { return find_root(a) == find_root(b); }
};

int main() {
    int n, m, q; scanf("%d%d%d", &n, &m, &q);
    vector<int> u(m), v(m), w(m);
    repeat (i,m) {
        scanf("%d%d%d", &u[i], &v[i], &w[i]);
        -- u[i]; -- v[i];
    }
    vector<int> xs(m); whole(iota, xs, 0);
    whole(sort, xs, [&](int x, int y) { return w[x] > w[y]; });
    while (q --) {
        int l, r; scanf("%d%d", &l, &r); -- l; -- r;
        int ans = -1;
        disjoint_sets t(2*n);
        for (int x : xs) if (l <= x and x <= r) {
            if (t.find_root(u[x]) == t.find_root(n+v[x])) continue; // required for the constant factor
            t.union_sets(u[x], n+v[x]);
            t.union_sets(v[x], n+u[x]);
            if (t.is_same(u[x], v[x])) {
                ans = w[x];
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}