Submission #3909

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3909	2013-08-31T09:20:46 Z	BalloonCollector	Cactus? Not cactus? (kriii1_C)	C++	1 / 1	72 ms	12152 KB

C

#include <cstdio>
#include <vector>

using namespace std;

typedef pair <int, int> ii;
int ch[100002], p[100002], c[100002], che[100002];
vector <ii> v[100002];
int cycle = 0;

void dfs(int u){
	if( cycle ) return ;
	
	ch[u] = 1;
	int si = v[u].size();

//	printf("%d\n", u);

	for(int i=0; i<si; i++){
		if( !che[v[u][i].second] ){
			che[v[u][i].second] = 1;
			
			if( !ch[v[u][i].first] ){
				p[v[u][i].first] = u;
				dfs( v[u][i].first );
			}
			else if( p[u] != v[u][i].first ){
				int pos = u;
				c[v[u][i].first] ++;
				if( c[v[u][i].first] >= 2 ) {
					cycle = 1;
					return;
				}
				//printf("cycle %d \n", v[u][i]);
				while( pos != v[u][i].first){
					//printf("p %d \n", pos);
					c[pos]++;
					if( c[pos] >= 2 ){
						cycle = 1;
						//puts("");
						return;
					}
					pos = p[pos];
				}
				//puts("");
				
			}
		}
	}
	
}

int main(){  //freopen("input.txt", "r", stdin);
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i=0; i<m; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		v[x].push_back(ii(y, i));
		v[y].push_back(ii(x, i));
	}

	dfs( 1 );

	/*for(int i=1; i<=n; i++)
		printf("%d ", c[i]);
	puts("");*/

	if( !cycle ) printf("Cactus\n");
	else printf("Not cactus\n");
	

 
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	5112 KB	Output is correct
2	Correct	0 ms	5112 KB	Output is correct
3	Correct	4 ms	5244 KB	Output is correct
4	Correct	0 ms	5112 KB	Output is correct
5	Correct	0 ms	5112 KB	Output is correct
6	Correct	0 ms	5244 KB	Output is correct
7	Correct	0 ms	5244 KB	Output is correct
8	Correct	4 ms	5244 KB	Output is correct
9	Correct	4 ms	5244 KB	Output is correct
10	Correct	48 ms	8412 KB	Output is correct
11	Correct	32 ms	8632 KB	Output is correct
12	Correct	40 ms	9208 KB	Output is correct
13	Correct	56 ms	8912 KB	Output is correct
14	Correct	48 ms	8984 KB	Output is correct
15	Correct	48 ms	10132 KB	Output is correct
16	Correct	44 ms	8448 KB	Output is correct
17	Correct	28 ms	9284 KB	Output is correct
18	Correct	72 ms	11364 KB	Output is correct
19	Correct	68 ms	12152 KB	Output is correct
20	Correct	36 ms	8916 KB	Output is correct
21	Correct	68 ms	8504 KB	Output is correct
22	Correct	48 ms	10548 KB	Output is correct
23	Correct	0 ms	5112 KB	Output is correct
24	Correct	0 ms	5112 KB	Output is correct
25	Correct	4 ms	5612 KB	Output is correct
26	Correct	56 ms	7884 KB	Output is correct
27	Correct	16 ms	6432 KB	Output is correct
28	Correct	40 ms	7488 KB	Output is correct
29	Correct	44 ms	7620 KB	Output is correct
30	Correct	32 ms	8016 KB	Output is correct
31	Correct	44 ms	7488 KB	Output is correct
32	Correct	44 ms	7884 KB	Output is correct
33	Correct	56 ms	7884 KB	Output is correct
34	Correct	48 ms	7884 KB	Output is correct