Submission #3611

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3611	2013-08-31T06:57:07 Z	mjy0503	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	284 ms	25436 KB

C

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
int n,top2=-1,stack2[200001],stack[200001],top=-1,save[200001];
using namespace std;
vector<int> list[200001],list2[200001];
map<pair<int,int>,bool> edge;
map<pair<int,int>,bool>::iterator it;
bool check[100001],flag,backedge;
void back(int k){
	int i;
	stack[++top]=k;
	while(top!=-1){
		k=stack[top];
		check[k]=1;
		for(;save[k]<list[k].size();save[k]++){
			if(!check[list[k][save[k]]]){
				list2[list[k][save[k]]].push_back(k);
				edge.insert(make_pair(make_pair(list[k][save[k]],k),false));
				stack[++top]=list[k][save[k]];
				break;
			}
			else if(edge.find(make_pair(k,list[k][save[k]]))==edge.end()){
				edge.insert(make_pair(make_pair(list[k][save[k]],k),true));
				list2[list[k][save[k]]].push_back(k);
			}
		}
		if(save[k]==list[k].size()){
			top--;
			stack2[++top2]=k;
		}
	}
}
void flood(int k){
	int i;
	stack[++top]=k;
	while(top!=-1){
		k=stack[top];
		check[k]=1;
		for(;save[k]<list2[k].size();save[k]++){
			if(!check[list2[k][save[k]]]){
				it=edge.find(make_pair(k,list2[k][save[k]]));
				if(it->second){
					if(backedge)
						flag=1;
					backedge=1;
				}
				stack[++top]=list2[k][save[k]];
				break;
			}
		}
		if(save[k]==list2[k].size())
			top--;
	}
}
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));
	memset(save,0,sizeof(save));
	for(;top2>=0;top2--){
		backedge=0;
		if(!check[stack2[top2]])
			flood(stack2[top2]);
	}
	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	13028 KB	Output is correct
2	Correct	4 ms	13028 KB	Output is correct
3	Correct	4 ms	13556 KB	Output is correct
4	Correct	4 ms	13424 KB	Output is correct
5	Correct	4 ms	13424 KB	Output is correct
6	Correct	0 ms	13556 KB	Output is correct
7	Correct	8 ms	13688 KB	Output is correct
8	Correct	12 ms	13556 KB	Output is correct
9	Correct	4 ms	13556 KB	Output is correct
10	Correct	144 ms	23456 KB	Output is correct
11	Correct	108 ms	22124 KB	Output is correct
12	Correct	148 ms	20684 KB	Output is correct
13	Correct	184 ms	22268 KB	Output is correct
14	Correct	188 ms	21872 KB	Output is correct
15	Correct	200 ms	22664 KB	Output is correct
16	Correct	140 ms	20816 KB	Output is correct
17	Correct	144 ms	20288 KB	Output is correct
18	Correct	252 ms	24380 KB	Output is correct
19	Correct	284 ms	25436 KB	Output is correct
20	Correct	148 ms	20952 KB	Output is correct
21	Correct	236 ms	24512 KB	Output is correct
22	Correct	196 ms	23060 KB	Output is correct
23	Correct	0 ms	13160 KB	Output is correct
24	Correct	0 ms	13028 KB	Output is correct
25	Correct	4 ms	14216 KB	Output is correct
26	Correct	208 ms	24116 KB	Output is correct
27	Correct	80 ms	18044 KB	Output is correct
28	Correct	176 ms	22664 KB	Output is correct
29	Correct	192 ms	23060 KB	Output is correct
30	Correct	160 ms	23192 KB	Output is correct
31	Correct	176 ms	22664 KB	Output is correct
32	Incorrect	224 ms	24116 KB	Output isn't correct
33	Halted	0 ms	0 KB	-