http://codeforces.com/contest/687/problem/D

Summary:

n < 1000 vertices, m = O(n^2) weighted edges (numbered from 1 to m), and q < 1000 queries (L, R) to consider all edges number L to R, group the endpoints of the edges into two groups 0 or 1, and minimize the weight of the edge with the largest weight having its endpoints in the same group.

Solution:

The idea to solve the problem is interesting. Consider the query (L, R). If we go through all the edges numbered L to R in decreasing weight order, then for each edge (u, v) we will attempt to join the vertices u and v, which leads to three possibilities:

1. u and v are not in the same connected component. This means that u and v can be connected together and their connected components will form one larger connected components which is bipartite.

2. u and v are already in the same connected component. Before addition of edge u-v, the connected component is bipartite. Hence we need to check if the addition of u-v still maintains this property. This means we must check if u and v are in different group/color. If they are of different group, we can join them without problem.

3. Otherwise, u and v are of the same group/color. Hence u-v is the first edge such that its addition causes its connected component to be not bipartite. We conclude that the weight of edge u-v is the answer for the current query (L, R). [Contemplating about this further, here is why this is correct: we have proven to ourselves by construction that the answer to the query (L, R) is at most the weight of u-v, because we can indeed create bipartite components using all the edges of higher weight before u-v. To prove that the answer cannot be smaller than u-v, first observe that a cycle of odd length cannot be bipartite. Hence when u-v connects two vertices of the same color, we conclude that u-v introduces an odd cycle to the connected component. Hence there the edges from the highest weight to u-v cannot be bipartite due to the existence of the odd cycle, which means u-v must be the smallest possible answer to the query].

The implementation given here is not the most efficient one asymptotically (the expected solution seems to use segment tree of 'interesting' edges). It follows exactly the idea described above.

Implementation:

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> using namespace std; struct Edge { int u, v, weight, id; }; int n, m, q; int color[1010], par[1010], sz[1010]; vector<Edge> edges; void Init(){ for (int i=0;i<n;++i){ par[i]=i; color[i]=0; sz[i]=1; } } int FindPar(int u) { return par[u] == u ? u : (par[u] = FindPar(par[u])); } bool Combine(int u, int v) { int x = FindPar(u); int y = FindPar(v); if (x == y) { return color[u] != color[v]; } if (sz[x] > sz[y]) { swap(x, y); swap(u, v); } if (color[u] == color[v]) { for (int i=0;i<n;++i){ if (FindPar(i)==x) color[i] ^= 1; } } par[x] = y; if (sz[x] == sz[y]) sz[y]++; return true; } int Query(int L, int R) { Init(); for (int i=0;i<m;++i){ if(L <= edges[i].id && edges[i].id <= R) { if (!Combine(edges[i].u, edges[i].v)) return edges[i].weight; } } return -1; } int main(){ scanf("%d%d%d",&n,&m,&q); int u,v,w; for(int i=0;i<m;++i){ scanf("%d%d%d",&u,&v,&w); if (u > v) swap(u,v); --u; --v; edges.push_back({u, v, w, i}); } sort(edges.begin(), edges.end(), [](const Edge& L, const Edge& R) { return L.weight > R.weight; }); int l,r; for(int qq=0;qq<q;++qq){ scanf("%d%d",&l,&r); l--;r--; printf("%d\n",Query(l,r)); } return 0; }