Submission #3820

#	Time	Username	Problem	Language	Result	Execution time	Memory
3820		blmarket	Cactus? Not cactus? (kriii1_C)	C++98	1 / 1	64 ms	14200 KiB

C

#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 / 1