답안 #3595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
3595	2013-08-31T06:47:43 Z	mjy0503	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	304 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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	13028 KB	Output is correct
2	Correct	0 ms	13028 KB	Output is correct
3	Correct	8 ms	13556 KB	Output is correct
4	Correct	8 ms	13424 KB	Output is correct
5	Correct	4 ms	13424 KB	Output is correct
6	Correct	8 ms	13556 KB	Output is correct
7	Correct	12 ms	13688 KB	Output is correct
8	Correct	8 ms	13556 KB	Output is correct
9	Correct	12 ms	13556 KB	Output is correct
10	Correct	140 ms	23456 KB	Output is correct
11	Correct	120 ms	22124 KB	Output is correct
12	Correct	156 ms	20684 KB	Output is correct
13	Correct	172 ms	22268 KB	Output is correct
14	Correct	180 ms	21872 KB	Output is correct
15	Correct	204 ms	22664 KB	Output is correct
16	Correct	164 ms	20816 KB	Output is correct
17	Correct	148 ms	20288 KB	Output is correct
18	Correct	280 ms	24380 KB	Output is correct
19	Correct	304 ms	25436 KB	Output is correct
20	Correct	152 ms	20952 KB	Output is correct
21	Correct	260 ms	24512 KB	Output is correct
22	Correct	220 ms	23060 KB	Output is correct
23	Correct	0 ms	13160 KB	Output is correct
24	Correct	4 ms	13028 KB	Output is correct
25	Correct	12 ms	14216 KB	Output is correct
26	Correct	248 ms	24116 KB	Output is correct
27	Correct	84 ms	18044 KB	Output is correct
28	Correct	192 ms	22664 KB	Output is correct
29	Correct	208 ms	23060 KB	Output is correct
30	Correct	172 ms	23192 KB	Output is correct
31	Correct	196 ms	22664 KB	Output is correct
32	Incorrect	224 ms	24116 KB	Output isn't correct
33	Halted	0 ms	0 KB	-