oj.uz

Submission #23125

# Submission time Handle Problem Language Result Execution time Memory
23125 2017-05-03T10:35:54 Z model_code Pipes (CEOI15_pipes) C
30 / 100
 266 ms 14812 KB 
#include <stdio.h>
#include <stdlib.h>

#if 0
#define ASSERT(_x) do { if (!(_x)) { fprintf(stderr, "Assertion failure at line %d\n", __LINE__); exit(99); } } while (0)
#else
#define ASSERT(_x) do { } while (0)
#endif

#define MAXN 100000
#define MAXM 900000

#define MAXNN (MAXN+10)
#define MAXMM 2*(MAXM+10)

int N, M;

int first[MAXNN];

struct edge {
	int next;
	int dest;	// -1 if the edge was already used
};

struct edge edges[MAXMM];
int ne = 2;

void raw_add_edge(int x, int y)
{
	edges[ne].next = first[x];
	edges[ne].dest = y;
	first[x] = ne++;
}

void add_edge(int x, int y)
{
	raw_add_edge(x, y);
	raw_add_edge(y, x);
}

void chew(void)
{
	int cc = scanf("%d%d", &N, &M);
	ASSERT(cc == 2);
	ASSERT(N >= 1 && N <= MAXN);
	ASSERT(M >= 1 && M <= MAXM);

	int c = getchar();
	ASSERT(c == '\n');

	for (int i=0; i<M; i++) {
		int x, y;
		cc = scanf("%d%d", &x, &y);
		ASSERT(cc == 2);
		ASSERT(x >= 1 && x <= N && y >= 1 && y <= N);
		ASSERT(x != y);
		if (i < MAXM)
			add_edge(x, y);
		else
			exit(42);

		c = getchar();
		ASSERT(c == '\n');
	}

	ASSERT(getchar() < 0);
}

int enter[MAXNN];
int clock;

int dfs(int x)
{
	ASSERT(x >= 1 && x <= N);
	clock++;
	enter[x] = clock;
	int low = clock;
	for (int e=first[x]; e; e=edges[e].next) {
		int y = edges[e].dest;
		if (y >= 0) {
			int low2;
			if (enter[y])
				low2 = enter[y];
			else {
				edges[e^1].dest = -1;
				low2 = dfs(y);
				if (low2 < 0) {
					low2 = -low2;
					printf("%d %d\n", x, y);
				}
			}
			if (low2 < low)
				low = low2;
		}
	}
	return (low >= enter[x]) ? -low : low;
}

int main(void)
{
	chew();
	for (int i=1; i<=N; i++)
		if (!enter[i])
			dfs(i);
	return 0;
}

Compilation message

pipes.c: In function 'chew':
pipes.c:48:6: warning: variable 'c' set but not used [-Wunused-but-set-variable]
  int c = getchar();
      ^
pipes.c:43:6: warning: variable 'cc' set but not used [-Wunused-but-set-variable]
  int cc = scanf("%d%d", &N, &M);
      ^~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 9940 KB Output is correct
2 Correct 257 ms 9580 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 14348 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 241 ms 14556 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 207 ms 14644 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 209 ms 14724 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 216 ms 14780 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 219 ms 14812 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 213 ms 14696 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -