oj.uz

Submission #854837

# Submission time Handle Problem Language Result Execution time Memory
854837 2023-09-29T04:50:07 Z sugartheanh Colors (RMI18_colors) C++14
100 / 100
 1160 ms 18920 KB 
/**
 * 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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 10028 KB Output is correct
2 Correct 20 ms 9052 KB Output is correct
3 Correct 3 ms 8720 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 10324 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10068 KB Output is correct
2 Correct 20 ms 9048 KB Output is correct
3 Correct 5 ms 8540 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10068 KB Output is correct
2 Correct 20 ms 9048 KB Output is correct
3 Correct 5 ms 8540 KB Output is correct
4 Correct 115 ms 11600 KB Output is correct
5 Correct 528 ms 15600 KB Output is correct
6 Correct 885 ms 17876 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 10028 KB Output is correct
2 Correct 20 ms 9052 KB Output is correct
3 Correct 3 ms 8720 KB Output is correct
4 Correct 56 ms 10068 KB Output is correct
5 Correct 20 ms 9048 KB Output is correct
6 Correct 5 ms 8540 KB Output is correct
7 Correct 56 ms 9900 KB Output is correct
8 Correct 21 ms 9052 KB Output is correct
9 Correct 4 ms 8540 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 11556 KB Output is correct
2 Correct 478 ms 15616 KB Output is correct
3 Correct 616 ms 17848 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9396 KB Output is correct
2 Correct 14 ms 8792 KB Output is correct
3 Correct 7 ms 8540 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 10028 KB Output is correct
2 Correct 20 ms 9052 KB Output is correct
3 Correct 3 ms 8720 KB Output is correct
4 Correct 71 ms 10324 KB Output is correct
5 Correct 56 ms 10068 KB Output is correct
6 Correct 20 ms 9048 KB Output is correct
7 Correct 5 ms 8540 KB Output is correct
8 Correct 115 ms 11600 KB Output is correct
9 Correct 528 ms 15600 KB Output is correct
10 Correct 885 ms 17876 KB Output is correct
11 Correct 56 ms 9900 KB Output is correct
12 Correct 21 ms 9052 KB Output is correct
13 Correct 4 ms 8540 KB Output is correct
14 Correct 116 ms 11556 KB Output is correct
15 Correct 478 ms 15616 KB Output is correct
16 Correct 616 ms 17848 KB Output is correct
17 Correct 34 ms 9396 KB Output is correct
18 Correct 14 ms 8792 KB Output is correct
19 Correct 7 ms 8540 KB Output is correct
20 Correct 104 ms 10836 KB Output is correct
21 Correct 711 ms 15812 KB Output is correct
22 Correct 1160 ms 18920 KB Output is correct