oj.uz

Submission #3453

# Submission time Handle Problem Language Result Execution time Memory
3453 2013-08-31T05:53:08 Z wookayin Cactus? Not cactus? (kriii1_C) C++
1 / 1
 64 ms 14120 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n,e;
vector<int> graph[100000];
int t[100000];
int m[100000];
int tcnt;
 
//1 if ok
int dfs(int nod, int par)
{
    m[nod] = t[nod] = ++tcnt;
        int cnt = 0;
        for(int i = 0; i < graph[nod].size(); i++){
                int next = graph[nod][i];
                if (next == par) continue;
                if (t[next] != 0 && t[next] < t[nod]) {
                        // back edge
                        m[nod] = min(m[nod], t[next]);
                        cnt++;
                        if (cnt >= 2) 
                                return 0;
                } else  if (t[next] == 0) {
                        int res = dfs(next, nod);
                        m[nod] = min(m[nod], m[next]);
                        if (res == 0)
                                return 0;
                        if (t[nod] >= m[next]) {
                                cnt ++;
                                if (cnt >= 2)
                                        return 0;
                        }
                }
        }
        return 1;
}
 
int main()
{
        scanf("%d%d",&n,&e);
        for(int i = 0;i < e;i ++){
                int a,b;
                scanf("%d%d",&a,&b);
                a--,b--;
                graph[a].push_back(b);
                graph[b].push_back(a);
        }
        if (dfs(0, -1) == 0) {
                printf("Not cactus\n");
        } else {
                printf("Cactus\n");
        }
        return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4332 KB Output is correct
2 Correct 0 ms 4332 KB Output is correct
3 Correct 0 ms 4484 KB Output is correct
4 Correct 0 ms 4360 KB Output is correct
5 Correct 0 ms 4332 KB Output is correct
6 Correct 0 ms 4464 KB Output is correct
7 Correct 4 ms 4464 KB Output is correct
8 Correct 4 ms 4464 KB Output is correct
9 Correct 0 ms 4464 KB Output is correct
10 Correct 28 ms 7236 KB Output is correct
11 Correct 28 ms 7084 KB Output is correct
12 Correct 36 ms 10012 KB Output is correct
13 Correct 48 ms 8688 KB Output is correct
14 Correct 44 ms 8440 KB Output is correct
15 Correct 44 ms 11196 KB Output is correct
16 Correct 28 ms 8740 KB Output is correct
17 Correct 32 ms 10216 KB Output is correct
18 Correct 64 ms 12980 KB Output is correct
19 Correct 64 ms 14120 KB Output is correct
20 Correct 36 ms 9176 KB Output is correct
21 Correct 52 ms 8220 KB Output is correct
22 Correct 48 ms 11804 KB Output is correct
23 Correct 0 ms 4332 KB Output is correct
24 Correct 0 ms 4332 KB Output is correct
25 Correct 4 ms 5068 KB Output is correct
26 Correct 56 ms 7104 KB Output is correct
27 Correct 20 ms 5388 KB Output is correct
28 Correct 44 ms 6708 KB Output is correct
29 Correct 52 ms 6708 KB Output is correct
30 Correct 44 ms 6840 KB Output is correct
31 Correct 44 ms 6708 KB Output is correct
32 Correct 48 ms 7104 KB Output is correct
33 Correct 48 ms 7104 KB Output is correct
34 Correct 44 ms 7104 KB Output is correct