Submission #3892

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3892	2013-08-31T09:11:05 Z	BalloonCollector	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	148 ms	32768 KB

C

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef pair<int,int> ii;
map <ii,bool> mp;
vector<int> e[100001],cycle;
int n,m,a,b,f,asdf;
bool ch[100001];
void dfs(int v, vector<int> d){
	vector<int> tmp;
	int size=d.size();
	for(int i=0; i<size; i++){
		tmp.push_back(d[i]);
	}
	tmp.push_back(v);
	for(int i=size-2; i>=0; i--){
		if(tmp[i]==v){
			for(int j=i+1; j<size; j++){
				asdf=tmp[j];
				if(ch[asdf])
					f=1;
				ch[asdf]=1;
			}
		}
	}
	if(f)
		return ;
	size=e[v].size();
	for(int i=0; i<size; i++){
		if(!mp[ii(v,e[v][i])]){
			mp[ii(v,e[v][i])]=1;
			mp[ii(e[v][i],v)]=1;
				//tmp.push_back(e[v][i]);
			dfs(e[v][i],tmp);
				//tmp.pop_back();
		}
	
	}

}
int main(void){
	//freopen("input.txt","r",stdin);
	scanf("%d %d",&n,&m);
	for(int i=0; i<m; i++){
		scanf("%d %d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	vector<int> tmp;
	//tmp.push_back(a);
	dfs(a,tmp);
	
	if(f)
		puts("Not cactus");
	else puts("Cactus");
	return 0;

}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3948 KB	Output is correct
2	Correct	0 ms	3816 KB	Output is correct
3	Correct	28 ms	29260 KB	Output is correct
4	Correct	20 ms	16232 KB	Output is correct
5	Correct	16 ms	14024 KB	Output is correct
6	Correct	8 ms	4344 KB	Output is correct
7	Correct	8 ms	4604 KB	Output is correct
8	Correct	0 ms	4476 KB	Output is correct
9	Correct	8 ms	4464 KB	Output is correct
10	Correct	148 ms	16620 KB	Output is correct
11	Correct	132 ms	14892 KB	Output is correct
12	Memory limit exceeded	44 ms	32768 KB	Memory limit exceeded
13	Halted	0 ms	0 KB	-