oj.uz

답안 #4149

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4149 2013-09-02T12:38:40 Z pys7293 Cactus? Not cactus? (kriii1_C) C++
0 / 1
 160 ms 32768 KB 
#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

# 결과 실행 시간 메모리 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 -