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
#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;

}
# 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 -