Codeforces Round #360 (Div. 1) - D. Dividing Kingdom II

Problem Statement:
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;
}