Submission #4149

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4149	2013-09-02T12:38:40 Z	pys7293	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	160 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], Lv[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	4 ms	3680 KB	Output is correct
4	Correct	0 ms	3464 KB	Output is correct
5	Correct	4 ms	3132 KB	Output is correct
6	Correct	4 ms	3172 KB	Output is correct
7	Correct	4 ms	3304 KB	Output is correct
8	Correct	4 ms	3172 KB	Output is correct
9	Correct	4 ms	3304 KB	Output is correct
10	Correct	152 ms	21960 KB	Output is correct
11	Correct	160 ms	19300 KB	Output is correct
12	Memory limit exceeded	88 ms	32768 KB	Memory limit exceeded
13	Halted	0 ms	0 KB	-