Submission #1124465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124465		sleepntsheep	Port Facility (JOI17_port_facility)	C11	78 / 100	2431 ms	575724 KiB

port_facility

/*
 * https://mamnoonsiam.github.io/posts/joisc-2017-port-facility
 */

#include <stdio.h>
#include <stdlib.h>

#define N (1 << 20)
#define N_ (N*2)

#define M (1 << 25)

int n, a[N], b[N], aa[N_], *tt[N_ * 2], to[N_ * 2], vv[99], ll[99], rr[99], ii,
    jj, nxt[M], ww[M], yy[M], head[N], ptr[N_ * 2],
    qu[N], hd, tl, col[N], ans;

void link(int v, int w, int y)
{
  int i;
  i = ++jj;
  nxt[i] = head[v];
  ww[i] = w;
  yy[i] = y;
  head[v] = i;
}

void bilink(int v, int w, int y)
{
  link(v, w, y);
  link(w, v, y);
}

void pus(int i, int j)
{
  int o;
  o = to[i]++;
  if (!o)
    tt[i] = malloc(2 * sizeof **tt);
  else if (0 == (o & (o - 1)))
    tt[i] = realloc(tt[i], 2 * sizeof **tt * o);
  tt[i][o] = j;
}

void ins(int v, int l, int r, int p, int k)
{
  pus(v, k);
  if (l == r)
    return;
  if (p <= (l + r) / 2)
    ins(2 * v + 1, l, (l + r) / 2, p, k);
  else
    ins(2 * v + 2, (l + r) / 2 + 1, r, p, k);
}

void generate(int v, int l, int r, int x, int y)
{
  if (r < x || y < l)
    return;
  if (x <= l && r <= y)
  {
    vv[ii] = v;
    ll[ii] = l;
    rr[ii] = r;
    ++ii;
    return;
  }
  generate(2 * v + 1, l, (l + r) / 2, x, y);
  generate(2 * v + 2, (l + r) / 2 + 1, r, x, y);
}

void consider(int v, int ai)
{
  while (ptr[v] + 1 < to[v] && tt[v][ptr[v] + 1] < ai)
  {
    ++ptr[v];
    bilink(aa[tt[v][0]], aa[tt[v][ptr[v]]], 0);
  }
}

int main()
{
  int i, j;
  scanf("%d", &n);

  for (i = 1; i <= n; ++i)
  {
    scanf("%d%d", a + i, b + i);
    aa[a[i]] = i;
  }

  for (i = 1; i <= 2 * n; ++i)
    if (aa[i])
      ins(0, 1, 2 * n, b[aa[i]], i);

  for (i = 1; i <= n; ++i)
  {
    ii = 0;
    generate(0, 1, 2 * n, a[i] + 1, b[i] - 1);
    for (j = 0; j < ii; ++j)
    {
      if (0 == to[vv[j]])
        continue;
      if (tt[vv[j]][0] < a[i])
        bilink(i, aa[tt[vv[j]][0]], 3);
      consider(vv[j], a[i]);
    }
  }

  ans = 1;
  for (i = 1; i <= n; ++i)
  {
    if (col[i])
      continue;
    col[i] = 1;
    hd = tl = 0;
    qu[hd++] = i;
    while (hd > tl)
    {
      int v, j;
      v = qu[tl++];
      for (j = head[v]; j; j = nxt[j])
      {
        if (0 == col[ww[j]])
        {
          col[ww[j]] = col[v] ^ yy[j];
          qu[hd++] = ww[j];
        }
        else
        {
          if (col[ww[j]] != (col[v] ^ yy[j]))
          {
            puts("0");
            return 0;
          }
        }
      }
    }
    ans = ans * 2 % 1000000007;
  }

  printf("%d", ans);

  return 0;
}

Compilation message (stderr)

port_facility.c: In function 'main':
port_facility.c:83:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   scanf("%d", &n);
      |   ^~~~~~~~~~~~~~~
port_facility.c:87:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     scanf("%d%d", a + i, b + i);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 0 / 22