oj.uz

Submission #244322

# Submission time Handle Problem Language Result Execution time Memory
244322 2020-07-03T15:48:00 Z hihi Potemkin cycle (CEOI15_indcyc) C
70 / 100
 1000 ms 10232 KB 
/* O(e^2): for each edge uv, find shortest paths from v to neighbors of u not passing through the closed neighborhood of u,
   if any of them is non-trivial, we have a hole.  */

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

struct e
{
  int to;
  struct e *next, *prev, *opp;
};

static int n;
static int amark;
static struct vertex
{
  struct e ns;
  int target, dist, mark;
  struct e *from;
} *gr;
static int *queue;
static int qb, ql;

static struct e *
add_half (int x, int y)
{
  struct e *nw = malloc (sizeof (struct e));
  nw->to = y;
  nw->next = gr[x].ns.next;
  nw->prev = &gr[x].ns;
  nw->next->prev = nw;
  nw->prev->next = nw;
  return nw;
}

static void
add_edge (int x, int y)
{
  struct e *e1 = add_half (x, y);
  struct e *e2 = add_half (y, x);
  e1->opp = e2;
  e2->opp = e1;
}

static void
tgt_nbrs_of (int v, int t)
{
  struct e *ae;

  for (ae = gr[v].ns.next; ae->to != -1; ae = ae->next)
    gr[ae->to].target = t;
  gr[v].target = t;
}

static int
find_nontrivial_path (int f, int *tgt)
{
  amark++;
  qb = 0;
  ql = 1;
  queue[0] = f;
  gr[f].from = NULL;
  gr[f].dist = 0;
  gr[f].mark = amark;

  while (ql)
    {
      int v = queue[qb++];
      struct e *ae;
      ql--;

      for (ae = gr[v].ns.next; ae->to != -1; ae = ae->next)
	{
	  if (gr[ae->to].mark == amark)
	    continue;

	  gr[ae->to].mark = amark;
	  gr[ae->to].from = ae->opp;
	  gr[ae->to].dist = gr[v].dist + 1;

	  if (gr[ae->to].target)
	    {
	      if (gr[ae->to].dist > 1)
		{
		  *tgt = ae->to;
		  return 1;
		}
	    }
	  else
	    {
	      queue[qb + ql] = ae->to;
	      ql++;
	    }
	}
    }

  return 0;
}

static void
print_path (int v)
{
  for (; gr[v].from != NULL; v = gr[v].from->to)
    printf (" %d", v + 1);
  printf (" %d\n", v + 1);
}

int main (void)
{
  int m, i, x, y;
  struct e *ae;

  scanf ("%d %d", &n, &m);
  gr = malloc (n * sizeof (struct vertex));
  queue = malloc (n * sizeof (int));
  for (i = 0; i < n; i++)
    {
      gr[i].ns.to = -1;
      gr[i].ns.prev = gr[i].ns.next = gr[i].ns.opp = &gr[i].ns;
      gr[i].target = gr[i].dist = gr[i].mark = 0;
      gr[i].from = NULL;
    }

  for (i = 0; i < m; i++)
    {
      scanf ("%d %d", &x, &y);
      add_edge (x - 1, y - 1);
    }

  for (i = 0; i < n; i++)
    {
      tgt_nbrs_of (i, 1);
      for (ae = gr[i].ns.next; ae->to != -1; ae = ae->next)
	if (find_nontrivial_path (ae->to, &x))
	  {
	    printf ("%d", i + 1);
	    print_path (x);
	    return 0;
	  }
      tgt_nbrs_of (i, 0);
    }
  printf ("no\n");

  return 0;
}

Compilation message

indcyc.c: In function 'main':
indcyc.c:113:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d", &n, &m);
   ^~~~~~~~~~~~~~~~~~~~~~~
indcyc.c:126:7: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
       scanf ("%d %d", &x, &y);
       ^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 656 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 13 ms 896 KB Output is correct
4 Correct 262 ms 840 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 640 KB Output is correct
2 Correct 92 ms 640 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 5120 KB Output is correct
2 Correct 63 ms 2304 KB Output is correct
3 Execution timed out 1092 ms 5120 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 2432 KB Output is correct
2 Execution timed out 1092 ms 2304 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 10232 KB Output is correct
2 Execution timed out 1094 ms 10108 KB Time limit exceeded
3 Halted 0 ms 0 KB -