Submission #3499

#TimeUsernameProblemLanguageResultExecution timeMemory
3499Apple_CplusCactus? Not cactus? (kriii1_C)C++98
1 / 1
76 ms12320 KiB
#include <stdio.h> #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <sstream> #include <set> #include <map> #include <stack> #include <cmath> #include <cstdlib> #include <cstring> #include <string> using namespace std; #define ll long long #define pi pair<int,int> #define pll pair<ll,ll> #define pii pair<int,pi> #define X first #define Y second #define pb push_back #define ab(x) ((x)<0?(-(x)):(x)) #define xx(x) ((x)*(x)) #define mp make_pair #define vi vector<int> #define vll vector<ll> #define vs vector<string> #define vpi vector<pi> #define vpll vector<pll> #define ALL(x) (x).begin(),(x).end() #define Max (1<<30) #define LLMax (1ll<<60) template<class T>string ToString(T t){stringstream s;s<<t;return s.str();} template<class T>void ToOther(T&t,string a){stringstream s(a);s>>t;} int n,m; vi v[100005]; int dep[100005]; int P[100005]; int cy[100005]; bool ck[100005]; void go(int x,int p,int D){ ck[x]=1; dep[x]=D; P[x]=p; for(int i=0;i<v[x].size();i++){ int t=v[x][i]; if(t==p)continue; if(ck[t])continue; go(t,x,D+1); } } void END(){cout<<"Not cactus"<<endl;exit(0);} void calc(int a,int b){ int D=min(dep[a],dep[b]); while(dep[a]>D){ if(++cy[a]==2)END(); a=P[a]; } while(dep[b]>D){ if(++cy[b]==2)END(); b=P[b]; } while(a!=b){ if(++cy[a]==2)END(); if(++cy[b]==2)END(); a=P[a];b=P[b]; } if(++cy[a]==2)END(); } void dfs(int x,int p){ ck[x]=1; for(int i=0;i<v[x].size();i++){ int t=v[x][i];if(t==p)continue; if(ck[t]){ if(t<x)calc(t,x); continue; } dfs(t,x); } } int main(){ scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ int s,e;scanf("%d%d",&s,&e); v[s].pb(e);v[e].pb(s); } go(1,-1,0); memset(ck,0,sizeof(ck)); dfs(1,-1); cout<<"Cactus"<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...