Submission #23120

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
23120	2017-05-03T10:17:17 Z	model_code	Potemkin cycle (CEOI15_indcyc)	C	30 / 100	1000 ms	11068 KB

indcyc

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

#define MAXN 1000

static char adj[MAXN][MAXN];
struct vertex;

struct edge
{
  struct vertex *to;
  struct edge *next, *prev, *opp;
};

static int n;

struct vertex
{
  int id;
  struct edge ns;
};

struct graph
{
  int nv;
  struct vertex **vs;
};

static void
link (struct edge *e, struct vertex *at)
{
  e->next = at->ns.next;
  e->prev = &at->ns;
  e->next->prev = e;
  e->prev->next = e;
}

static struct edge *
add_half (struct vertex *x, struct vertex *y)
{
  struct edge *nw = malloc (sizeof (struct edge));
  nw->to = y;
  link (nw, x);
  return nw;
}

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

static void
init_graph (struct graph *g, int nv)
{
  int i;

  g->nv = nv;
  g->vs = malloc (n * sizeof (struct vertex *));
  for (i = 0; i < n; i++)
    {
      g->vs[i] = malloc (sizeof (struct vertex));
      g->vs[i]->ns.to = NULL;
      g->vs[i]->ns.opp = NULL;
      g->vs[i]->ns.prev = g->vs[i]->ns.next = &g->vs[i]->ns;
      g->vs[i]->id = i;
    }
}


int main (void)
{
  int m, i, x, y;
  struct graph g;
  struct edge *e, *e1, *e2;

  scanf ("%d %d", &n, &m);
  init_graph (&g, n);
  for (i = 0; i < m; i++)
    {
      scanf ("%d %d", &x, &y);
      add_edge (g.vs[x - 1], g.vs[y - 1]);
      adj[x - 1][y - 1] = adj[y - 1][x - 1] = 1;
    }

  for (i = 0; i < n; i++)
    for (e = g.vs[i]->ns.next; e->to; e = e->next)
      {
	if (e->to->id < i)
	  continue;

	for (e1 = e->to->ns.next; e1->to; e1 = e1->next)
	  {
	    if (e1->to->id <= i || adj[i][e1->to->id])
	      continue;

	    for (e2 = e1->to->ns.next; e2->to; e2 = e2->next)
	      if (e2->to != e->to
		  && !adj[e2->to->id][e->to->id]
		  && adj[e2->to->id][i])
		{
		  printf ("%d %d %d %d\n", i + 1, e->to->id + 1, e1->to->id + 1, e2->to->id + 1);
		  return 0;
		}
	  }
      }

  printf ("no\n");

  return 0;
}

Compilation message

indcyc.c: In function 'main':
indcyc.c:80:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d", &n, &m);
   ^
indcyc.c:84: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	Memory	Grader output
1	Correct	2092 KB	Output is correct
2	Correct	2092 KB	Output is correct
3	Correct	2092 KB	Output is correct
4	Correct	2092 KB	Output is correct
5	Correct	2092 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2092 KB	Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	2092 KB	Expected integer, but "no" found

Subtask #5
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	2092 KB	Expected integer, but "no" found
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2356 KB	Output is correct
2	Incorrect	3 ms	2356 KB	Expected integer, but "no" found
3	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	29 ms	2356 KB	Expected integer, but "no" found
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	6580 KB	Execution timed out
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	3940 KB	Execution timed out
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	11068 KB	Execution timed out
2	Halted	0 ms	0 KB	-