oj.uz

Submission #23124

# Submission time Handle Problem Language Result Execution time Memory
23124 2017-05-03T10:35:23 Z model_code Pipes (CEOI15_pipes) C++14
100 / 100
 1480 ms 12088 KB 
#include <stdio.h>

#define MAXM 300000
#define MAXN 100000

enum {
  REDUNDANT,
  BRIDGE,
  NEEDED,
};

static struct edge
{
  int u, v;
  int state;
} es[MAXM];
static int nes;

static struct edge *ns[2 * MAXM];
static int elb[MAXN + 2];
static int level[MAXN];
static enum {UNVISITED, OPEN, CLOSED} state[MAXN];

static int component[MAXN];
static int acomp;
static int comp_stack[MAXN];
static int csn;

static int
other_end (struct edge *e, int x)
{
  return e->u == x ? e->v : e->u;
}

static struct
{
  int v, pos, lev_back;
  struct edge *best_back;
} stack[MAXN];
static int st_top;

static void
dfs (int v)
{
  level[v] = 0;
  state[v] = OPEN;
  stack[0].v = v;
  stack[0].pos = elb[v];
  stack[0].lev_back = 0;
  stack[0].best_back = NULL;
  st_top = 1;

  comp_stack[0] = v;
  csn = 1;

  while (st_top)
    {
      int u, p, lb, w;
      struct edge *bb, *from, *e;
      
      u = stack[st_top - 1].v;
      p = stack[st_top - 1].pos;
      lb = stack[st_top - 1].lev_back;
      bb = stack[st_top - 1].best_back;
      from = st_top > 1 ? ns[stack[st_top - 2].pos - 1] : NULL;

      if (p == elb[u + 1])
	{
	  st_top--;
	  state[u] = CLOSED;

	  if (bb)
	    {
	      from->state = NEEDED;
	      bb->state = NEEDED;

	      if (stack[st_top - 1].lev_back > lb)
		{
		  stack[st_top - 1].lev_back = lb;
		  stack[st_top - 1].best_back = bb;
		}
	    }
	  else
	    {
	      do
		{
		  w = comp_stack[--csn];
		  component[w] = acomp;
		} while (w != u);
	      acomp++;
	    }
	  continue;
	}

      stack[st_top - 1].pos++;
      e = ns[p];
      if (e == from)
	continue;
      w = other_end (e, u);

      if (state[w] == CLOSED)
	continue;

      if (state[w] == OPEN)
	{
	  if (level[w] < lb)
	    {
	      stack[st_top - 1].lev_back = level[w];
	      stack[st_top - 1].best_back = e;
	    }

	  continue;
	}

      state[w] = OPEN;
      level[w] = level[u] + 1;
      stack[st_top].v = w;
      stack[st_top].pos = elb[w];
      stack[st_top].lev_back = level[w];
      stack[st_top].best_back = NULL;
      e->state = BRIDGE;
      st_top++;

      comp_stack[csn++] = w;
    }
}

static void
classify_edges (int n)
{
  int i;

  for (i = 0; i < n + 2; i++)
    elb[i] = 0;

  for (i = 0; i < nes; i++)
    {
      es[i].state = REDUNDANT;
      elb[es[i].u + 2]++;
      elb[es[i].v + 2]++;
    }
  for (i = 3; i < n + 2; i++)
    elb[i] += elb[i - 1];

  for (i = 0; i < nes; i++)
    {
      ns[elb[es[i].u + 1]++] = es + i;
      ns[elb[es[i].v + 1]++] = es + i;
    }

  for (i = 0; i < n; i++)
    state[i] = UNVISITED;

  acomp = 0;
  for (i = 0; i < n; i++)
    if (state[i] == UNVISITED)
      dfs (i);
}

int main (void)
{
  int n, m, i, j, k;

  scanf ("%d%d", &n, &m);

  for (i = 0; i < n; i++)
    component[i] = i;

  for (i = 0; i < m; i++)
    {
      int u, v;
      scanf ("%d%d", &u, &v);

      if (component[u - 1] == component[v - 1])
	continue;

      es[nes].u = u - 1;
      es[nes].v = v - 1;
      nes++;

      if (nes == 3 * n)
	{
	  classify_edges (n);
	  k = 0;

	  for (j = 0; j < nes; j++)
	    if (es[j].state != REDUNDANT)
	      es[k++] = es[j];
	  nes = k;
	}
    }
  classify_edges (n);
  for (j = 0; j < nes; j++)
    if (es[j].state == BRIDGE)
      printf ("%d %d\n", es[j].u + 1, es[j].v + 1);

  return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:164:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &n, &m);
   ~~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:172:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf ("%d%d", &u, &v);
       ~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 848 KB Output is correct
2 Correct 4 ms 768 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 768 KB Output is correct
2 Correct 109 ms 768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 1536 KB Output is correct
2 Correct 226 ms 1356 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 3084 KB Output is correct
2 Correct 263 ms 3620 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 8648 KB Output is correct
2 Correct 429 ms 7548 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 9876 KB Output is correct
2 Correct 662 ms 9220 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1033 ms 12088 KB Output is correct
2 Correct 907 ms 10660 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1204 ms 12076 KB Output is correct
2 Correct 1100 ms 10664 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1480 ms 11484 KB Output is correct
2 Correct 1279 ms 11512 KB Output is correct