Saturday, July 23, 2016

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

Problem Statement:

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.

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.


#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){
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) {
  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(){
  int u,v,w;
  for(int i=0;i<m;++i){
    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){
  return 0;