Submission #3563

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3563	2013-08-31T06:36:23 Z	mjy0503	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	176 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	4 ms	7020 KB	Output is correct
4	Correct	4 ms	6900 KB	Output is correct
5	Correct	4 ms	6832 KB	Output is correct
6	Correct	4 ms	6912 KB	Output is correct
7	Correct	4 ms	7044 KB	Output is correct
8	Correct	4 ms	6912 KB	Output is correct
9	Correct	8 ms	6912 KB	Output is correct
10	Correct	120 ms	16812 KB	Output is correct
11	Correct	84 ms	15480 KB	Output is correct
12	Correct	132 ms	20252 KB	Output is correct
13	Correct	152 ms	19280 KB	Output is correct
14	Correct	152 ms	18712 KB	Output is correct
15	Correct	176 ms	23276 KB	Output is correct
16	Correct	128 ms	18340 KB	Output is correct
17	Correct	120 ms	20396 KB	Output is correct
18	Runtime error	176 ms	27212 KB	Program hung waiting for input
19	Halted	0 ms	0 KB	-