Submission #854837

#	Time	Username	Problem	Language	Result	Execution time	Memory
854837		sugartheanh	Colors (RMI18_colors)	C++14	100 / 100	1160 ms	18920 KiB

colors

/**
 * Process vertices in decreasing order of a, in blocks of sqrt(n) at a
 * time. Build a disjoint set forest using vertices that are present in the
 * graph for the entire block, then for each color test connectivity on that
 * forest plus other relevant vertices.
 *
 * Author: Catalin Francu
 **/
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 150000
#define MAX_M 200000
#define NIL -1

typedef struct {
  int node, next;
} cell;

typedef struct {
  int u, v;
} edge;

/* color data */
int a[MAX_N], b[MAX_N];
int alist[MAX_N], blist[MAX_N]; /* head pointers of color lists */
cell c[2 * MAX_N];              /* buffer for color lists */
int numColors;

/* graph data */
edge e[MAX_M];       /* edge list */
int dsf[MAX_N];      /* disjoint set forest */
int m, n;

/* block-level graph data */
edge be[MAX_M];      /* edge list */
int bm;              /* number of edges */
int bd[MAX_N];       /* disjoint set forest */

/* other data */
int seen[MAX_N + 1]; /* for counting things */

int edgeCmp(const void* x, const void* y) {
  return a[((edge*)y)->v] - a[((edge*)x)->v];
}

/* renumber colors to eliminate gaps */
void renumberColors() {
  int i, u;

  numColors = 0;
  for (i = 1; i <= n; i++) {
    seen[i] = 0;
  }
  for (u = 0; u < n; u++) {
    seen[a[u]] = seen[b[u]] = 1;
  }
  for (i = 1; i <= n; i++) {
    if (seen[i]) {
      seen[i] = numColors++;
    }
  }
  for (u = 0; u < n; u++) {
    a[u] = seen[a[u]];
    b[u] = seen[b[u]];
  }

  /* reset seen[] for connectivity testing */
  for (i = 0; i < n; i++) {
    seen[i] = numColors;
  }
}

/* read colors and build vertex lists for every color */
void readColors() {
  int i, u;

  for (u = 0; u < n; u++) {
    scanf("%d", &a[u]);
  }
  for (u = 0; u < n; u++) {
    scanf("%d", &b[u]);
  }

  renumberColors();

  int ptr = 0;
  for (i = 0; i < numColors; i++) {
    alist[i] = blist[i] = NIL;
  }
  for (u = 0; u < n; u++) {
    c[ptr].node = u;
    c[ptr].next = alist[a[u]];
    alist[a[u]] = ptr++;

    c[ptr].node = u;
    c[ptr].next = blist[b[u]];
    blist[b[u]] = ptr++;
  }
}

/* read edges and sort them by min(a[u], a[v]) (decreasing) */
void readGraph() {
  int i, u, v;

  for (i = 0; i < m; i++) {
    scanf("%d%d", &u, &v);
    u--; v--;
    if (a[u] < a[v]) {
      int tmp = u;
      u = v;
      v = tmp;
    }
    e[i] = (edge) { u, v };
  }

  qsort(e, m, sizeof(edge), edgeCmp);
}

inline int dsfFind(int* f, int x) {
  int root = x;
  do {
    root = f[root];
  } while (f[root] != root);

  /* path compression */
  while (f[x] != root) {
    int tmp = f[x];
    f[x] = root;
    x = tmp;
  }

  return root;
}

inline void dsfUnion(int* f, int x, int y) {
  f[dsfFind(f, x)] = dsfFind(f, y);
}

/* given a high color, find a corresponding low color so that the interval */
/* has O(sqrt(n)) vertices */
int findBlock(int hi) {
  int lo = hi + 1, size = 2 * sqrt(n);

  while (lo > 0 && size >= 0) {
    lo--;

    /* count vertices covered by this new lo */
    for (int p = alist[lo]; p != NIL; p = c[p].next) {
      size--;
    }
    for (int p = blist[lo]; p != NIL; p = c[p].next) {
      int u = c[p].node;
      size -= (a[u] > hi);
    }
  }

  return lo;
}

/* build disjoint set structures limited to edges between vertices */
/* of the form a > hi, b < lo */
void buildSets(int lo, int hi) {
  for (int u = 0; u < n; u++) {
    dsf[u] = u;
  }

  int i = 0;
  while (i < m && a[e[i].v] > hi) {    /* then a[u] and a[v] are both > hi */
    if (b[e[i].u] < lo && b[e[i].v] < lo) {
      dsfUnion(dsf, e[i].u, e[i].v);
    }
    i++;
  }
}

/* collect (a) edges within the current block and (b) edges from the current */
/* block to the inner rectangle */
void collectBlockEdges(int lo, int hi) {
  bm = 0;

  int i = 0;
  while (i < m && a[e[i].v] >= lo) {
    int u = e[i].u, v = e[i].v;
    /* both are in the current block, but not both are in the inner rectangle */
    if (b[u] <= hi &&
        b[v] <= hi &&
        (a[v] <= hi || b[u] >= lo || b[v] >= lo)) {
      be[bm++] = (edge) { dsfFind(dsf, u), dsfFind(dsf, v) };
    }
    i++;
  }
}

/* Disjoint set forests for the current color. These need to be computed */
/* carefully in order to explore only O(sqrt(n)) vertices and avoid */
/* overflowing into the entire graph. */
void buildBlockSets(int col) {
  /* initialize endpoints of collected edges plus any isolated vertices */
  for (int i = 0; i < bm; i++) {
    bd[be[i].u] = be[i].u;
    bd[be[i].v] = be[i].v;
  }
  for (int p = alist[col]; p != NIL; p = c[p].next) {
    bd[c[p].node] = c[p].node;
  }
  for (int p = blist[col]; p != NIL; p = c[p].next) {
    bd[c[p].node] = c[p].node;
  }

  /* union-find on valid edges for this color */
  int i = 0;
  while (i < bm && a[be[i].v] >= col) {
    if (b[be[i].u] <= col && b[be[i].v] <= col) {
      dsfUnion(bd, be[i].u, be[i].v);
    }
    i++;
  }
}

/* true if all vertices having b = col are reachable from vertices */
/* having a = col */
int satisfiable(int col) {
  /* for all u having a[u] = col, mark u's component as seen */
  for (int p = alist[col]; p != NIL; p = c[p].next) {
    seen[dsfFind(bd, c[p].node)] = col;
  }

  /* for all v having b[v] = col, ensure that v's component is seen */
  int p = blist[col];
  while (p != NIL && seen[dsfFind(bd, c[p].node)] == col) {
    p = c[p].next;
  }
  return (p == NIL);
}

int main() {
  int numTests;

  scanf("%d", &numTests);

  while (numTests--) {
    scanf("%d%d", &n, &m);
    readColors();
    readGraph();

    int hi = numColors - 1, ok = 1;

    while (hi >= 0 && ok) {
      /* compute block-level data */
      int lo = findBlock(hi);
      buildSets(lo, hi);
      collectBlockEdges(lo, hi);

      /* check that all colors hi...lo are satisfiable */
      while (hi >= lo && ok) {
        buildBlockSets(hi);
        ok = satisfiable(hi);
        hi--;
      }
    }

    printf("%d\n", ok);
  }

  return 0;
}

Compilation message (stderr)

colors.cpp: In function 'void readColors()':
colors.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     scanf("%d", &a[u]);
      |     ~~~~~^~~~~~~~~~~~~
colors.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     scanf("%d", &b[u]);
      |     ~~~~~^~~~~~~~~~~~~
colors.cpp: In function 'void readGraph()':
colors.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~
colors.cpp: In function 'int main()':
colors.cpp:241:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |   scanf("%d", &numTests);
      |   ~~~~~^~~~~~~~~~~~~~~~~
colors.cpp:244:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  244 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22