Submission #3781

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3781	2013-08-31T08:18:27 Z	cki86201	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	76 ms	12172 KB

C

#include<stdio.h>
#include<vector>
using namespace std;

vector<int> edge[100000];
vector<int> now;
bool check[100000]={0};
bool check_cycle[100000]={0};
bool ans=false;
int distime[100000]={0},deltime[100000]={0},time=0;
void dfs(int a,int par){
	check[a]=true;
	distime[a]=time++;
	now.push_back(a);
	int i,j;
	for(i=0;i<edge[a].size();i++){
		if(check[edge[a][i]] && edge[a][i]!=par && distime[edge[a][i]]<distime[a]){
			if(check_cycle[edge[a][i]]){
				ans=true;
				return;
			}
			else{
				for(j=now.size()-1;j>=0;j--){
					check_cycle[now[j]]=true;
					if(now[j]==edge[a][i]) break;
				}
			}
		}
		else if(!check[edge[a][i]]){
			dfs(edge[a][i],a);
			if(ans) return;
		}
	}
	deltime[a]=time++;
	now.pop_back();
}
int main()
{
	int i,n,m,a,b;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d%d",&a,&b);
		edge[a-1].push_back(b-1);
		edge[b-1].push_back(a-1);
	}
	dfs(0,0);
	if(ans) printf("Not cactus");
	else printf("Cactus");
	return 0;
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	4528 KB	Output is correct
2	Correct	0 ms	4528 KB	Output is correct
3	Correct	4 ms	4660 KB	Output is correct
4	Correct	4 ms	4660 KB	Output is correct
5	Correct	0 ms	4528 KB	Output is correct
6	Correct	0 ms	4660 KB	Output is correct
7	Correct	0 ms	4660 KB	Output is correct
8	Correct	0 ms	4660 KB	Output is correct
9	Correct	4 ms	4660 KB	Output is correct
10	Correct	44 ms	7432 KB	Output is correct
11	Correct	36 ms	7280 KB	Output is correct
12	Correct	40 ms	8984 KB	Output is correct
13	Correct	48 ms	8100 KB	Output is correct
14	Correct	44 ms	7868 KB	Output is correct
15	Correct	52 ms	9864 KB	Output is correct
16	Correct	32 ms	8296 KB	Output is correct
17	Correct	40 ms	9056 KB	Output is correct
18	Correct	76 ms	11384 KB	Output is correct
19	Correct	60 ms	12172 KB	Output is correct
20	Correct	36 ms	8516 KB	Output is correct
21	Correct	60 ms	8060 KB	Output is correct
22	Correct	56 ms	10244 KB	Output is correct
23	Correct	0 ms	4528 KB	Output is correct
24	Incorrect	0 ms	4528 KB	Output isn't correct
25	Halted	0 ms	0 KB	-