oj.uz

답안 #3820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3820 2013-08-31T08:34:39 Z blmarket Cactus? Not cactus? (kriii1_C) C++
1 / 1
 64 ms 14200 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <numeric>
#include <iterator>
#include <queue>
#include <set>
#include <map>
#include <vector>

#define mp make_pair
#define pb push_back
#define sqr(x) ((x)*(x))
#define foreach(it,c) for(typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;

template<typename T> int size(const T &a) { return a.size(); } 

int N,M;
VVI links;
int depth[100005];
bool ret = false;

int go(int a, int b, int d) {
    depth[a] = d;
    int cnt = 0;
    int mind = d;
    for(int i=0;i<size(links[a]);i++) {
        int np = links[a][i];
        if(np == b) continue;
        // cout << a << " " << np << " (" << b << ") " << cnt << endl;

        if(depth[np] != -1 && depth[np] < d) {
            mind = depth[np];
            cnt++;
        }

        if(depth[np] != -1) {
            continue;
        }

        int tmp = go(np, a, d+1);
        if(tmp <= d) cnt++;
        mind = min(mind, tmp);
    }

    if(cnt > 1) {
        // cout << a << " " << b << " " << d << endl;
        ret = true;
    }

    return mind;
}

int main(void)
{
    scanf("%d %d", &N, &M);
    links.resize(N+1);
    for(int i=0;i<M;i++) {
        int a,b;
        scanf("%d %d", &a, &b);
        links[a].pb(b);
        links[b].pb(a);
    }

    memset(depth, -1, sizeof(depth));
    go(1, -1, 0);

    if(ret) {
        cout << "Not cactus" << endl;
    } else {
        cout << "Cactus" << endl;
    }
    return 0;
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2068 KB Output is correct
2 Correct 0 ms 2068 KB Output is correct
3 Correct 0 ms 2220 KB Output is correct
4 Correct 0 ms 2232 KB Output is correct
5 Correct 0 ms 2200 KB Output is correct
6 Correct 0 ms 2332 KB Output is correct
7 Correct 0 ms 2332 KB Output is correct
8 Correct 0 ms 2200 KB Output is correct
9 Correct 0 ms 2332 KB Output is correct
10 Correct 40 ms 6864 KB Output is correct
11 Correct 24 ms 6440 KB Output is correct
12 Correct 32 ms 9208 KB Output is correct
13 Correct 40 ms 8032 KB Output is correct
14 Correct 48 ms 7664 KB Output is correct
15 Correct 44 ms 10760 KB Output is correct
16 Correct 36 ms 7952 KB Output is correct
17 Correct 28 ms 9316 KB Output is correct
18 Correct 64 ms 12872 KB Output is correct
19 Correct 64 ms 14200 KB Output is correct
20 Correct 32 ms 8400 KB Output is correct
21 Correct 60 ms 8112 KB Output is correct
22 Correct 48 ms 11440 KB Output is correct
23 Correct 0 ms 2068 KB Output is correct
24 Correct 0 ms 2068 KB Output is correct
25 Correct 4 ms 3036 KB Output is correct
26 Correct 52 ms 6924 KB Output is correct
27 Correct 24 ms 4008 KB Output is correct
28 Correct 44 ms 6268 KB Output is correct
29 Correct 52 ms 6268 KB Output is correct
30 Correct 44 ms 6400 KB Output is correct
31 Correct 44 ms 6268 KB Output is correct
32 Correct 56 ms 6924 KB Output is correct
33 Correct 44 ms 6924 KB Output is correct
34 Correct 56 ms 6924 KB Output is correct