Submission #4138

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4138	2013-09-02T09:34:24 Z	pys7293	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	168 ms	32768 KB

C

#include <algorithm>
#include <cstdio>
#include <map>
#include <memory.h>
#include <vector>

using namespace std;

int N, M;
int Lv[111111], C;
int Lo[111111];

map<int, map<int, bool> > Chk;

vector<vector<int> > L;

void DFS(int i, int P)
{
	if (Lv[i] == 0) Lv[i] = Lo[i] = ++C;
	for (int j = 0; j < L[i].size(); j++) {
		if (P == L[i][j]) continue;
		if (Lv[L[i][j]] == 0) {
			DFS(L[i][j], i);
			Lo[i] = min(Lo[i], Lo[L[i][j]]);
			if (Lv[i] < Lo[L[i][j]]) Chk[i][L[i][j]] = Chk[L[i][j]][i] = true;
		} else Lo[i] = min(Lo[i], Lo[L[i][j]]);
	}
}

int main(void)
{
	scanf("%d%d", &N, &M);
	L.resize(N + 1);
	for (int i = 1; i <= M; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		L[u].push_back(v);
		L[v].push_back(u);
	}
	DFS(1, 0);
	bool Ans = true;
	for (int i = 1; i <= N; i++) {
		if (!Ans) break;
		int CC = 0;
		for (int j = 0; j < L[i].size(); j++) {
			if (Chk[i][L[i][j]]) continue;
			CC++;
		}
		if (!(CC == 0 || CC == 2)) Ans = false;
	}
	printf("%s\n", Ans ? "Cactus" : "Not cactus");

	return 0;
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2116 KB	Output is correct
2	Correct	0 ms	2116 KB	Output is correct
3	Correct	0 ms	3676 KB	Output is correct
4	Correct	4 ms	3464 KB	Output is correct
5	Correct	4 ms	3136 KB	Output is correct
6	Correct	4 ms	3172 KB	Output is correct
7	Correct	4 ms	3304 KB	Output is correct
8	Correct	0 ms	3172 KB	Output is correct
9	Correct	4 ms	3304 KB	Output is correct
10	Correct	168 ms	21960 KB	Output is correct
11	Correct	152 ms	19300 KB	Output is correct
12	Memory limit exceeded	96 ms	32768 KB	Memory limit exceeded
13	Halted	0 ms	0 KB	-