Submission #3565

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3565	2013-08-31T06:37:12 Z	tncks0121	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	152 ms	27212 KB

C

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
int n,top=-1,stack[100001];
using namespace std;
vector<int> list[100001],list2[100001];
map<pair<int,int>,bool> edge;
map<pair<int,int>,bool>::iterator it;
bool check[100001],flag,backedge;
void back(int k){
	int i;
	check[k]=1;
	for(i=0;i<list[k].size();i++){
		if(!check[list[k][i]]){
			list2[list[k][i]].push_back(k);
			edge.insert(make_pair(make_pair(list[k][i],k),false));
			back(list[k][i]);
		}
		else if(edge.find(make_pair(k,list[k][i]))==edge.end()){
			edge.insert(make_pair(make_pair(list[k][i],k),true));
			list2[list[k][i]].push_back(k);
		}
	}
	stack[++top]=k;
}
void flood(int k){
	int i;
	check[k]=1;
	for(i=0;i<list2[k].size();i++){
		if(!check[list2[k][i]]){
			it=edge.find(make_pair(k,list2[k][i]));
			if(it->second){
				if(backedge)
					flag=1;
				backedge=1;
			}
			flood(list2[k][i]);
		}
	}
	stack[++top]=k;
}
int main(){
	int m,i,a,b;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d %d",&a,&b);
		a--;b--;
		list[a].push_back(b);
		list[b].push_back(a);
	}
	for(i=0;i<n;i++){
		if(!check[i])
			back(i);
	}
	memset(check,0,sizeof(check));
	for(;top>=0;top--){
		backedge=0;
		if(!check[stack[top]])
			flood(stack[top]);
	}
	if(flag)
		printf("Not cactus\n");
	else
		printf("Cactus\n");
	return 0;
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	6384 KB	Output is correct
2	Correct	0 ms	6384 KB	Output is correct
3	Correct	8 ms	7016 KB	Output is correct
4	Correct	0 ms	6904 KB	Output is correct
5	Correct	0 ms	6832 KB	Output is correct
6	Correct	8 ms	6912 KB	Output is correct
7	Correct	8 ms	7044 KB	Output is correct
8	Correct	4 ms	6912 KB	Output is correct
9	Correct	0 ms	6912 KB	Output is correct
10	Correct	112 ms	16812 KB	Output is correct
11	Correct	84 ms	15480 KB	Output is correct
12	Correct	120 ms	20256 KB	Output is correct
13	Correct	152 ms	19284 KB	Output is correct
14	Correct	148 ms	18708 KB	Output is correct
15	Correct	152 ms	23276 KB	Output is correct
16	Correct	128 ms	18340 KB	Output is correct
17	Correct	120 ms	20392 KB	Output is correct
18	Runtime error	152 ms	27212 KB	Program hung waiting for input
19	Halted	0 ms	0 KB	-