oj.uz

답안 #4138

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4138 2013-09-02T09:34:24 Z pys7293 Cactus? Not cactus? (kriii1_C) C++
0 / 1
 168 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], 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

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