Problem D solution went into infinite loop on test case #115

Правка en1, от rohitranjan017, 2016-08-30 00:26:14

I am trying to implement Kosaraju for question 369 D but i guess it goes into some into some infinite loop on test case #115. I am not able to figure out why is it so. Here is my code

include<bits/stdc++.h>

define up(j,k,i) for(i=j;i<k;i++)

define down(j,k,i) for(i=j;i>k;i--)

define M 1000000007

define pp(n) printf("%lld\n",ll(n))

define ps(n) printf("%lld ",ll(n))

define pd(x,y) printf("%lld %lld\n",ll(x),ll(y))

define is(n) scanf("%lld",&n)

define Max(x,y) max(ll(x),ll(y))

define Min(x,y) min(ll(x),ll(y))

define inf LLONG_MAX

define id(n,m) scanf("%lld%lld",&n,&m)

define it(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)

define ss(s) scanf("%s",s)

define cool 0

define pb push_back

define mp make_pair

define F first

define S second

define pll pair<ll,ll>

define db cout<<"######\n"

define null(a) memset(a,0,sizeof(a))

define neg(a) memset(a,255,sizeof(a))

typedef long double ld; typedef long long int ll; using namespace std; ll i,j,k,z,t,n,m,sum,ans,x,y,maxm=0,minm=inf; map<ll,ll> child;

vector par[200005];

bool vis[200005],revis[200005],permvis[200005];

stack s;

ll fact[400005];

void dfs(ll x) {

if(vis[x]) return;

vis[x]=1;

dfs(child[x]);

s.push(x); }

void rev_dfs(ll x,ll cnt) {

permvis[x]=1;

revis[x]=1;

for(auto c:par[x])

if(revis[c]!=1)
rev_dfs(c,cnt+1);

else if(revis[c])
z=1,ans=cnt+1;

revis[x]=0;

} int main() { fact[0]=1; sum=1;

is(n);

up(1,n+1,i) fact[i]=fact[i-1]*2%M;

up(1,n+1,i) { is(x); child[i]=x; par[x].pb(i); }

up(1,n+1,i) if(!vis[i]) dfs(i);

while(!s.empty()) { ans=0; z=0;

x=s.top();
s.pop();

if(permvis[x]) 
continue;

rev_dfs(x,0);

if(z) sum=sum*(fact[ans]-2)%M,y+=ans;

}

sum=sum*(fact[n-y])%M;

pp((sum+M)%M);

}

Теги 369, kosaraju

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский rohitranjan017 2016-08-30 14:43:48 997
en2 Английский rohitranjan017 2016-08-30 00:28:21 625
en1 Английский rohitranjan017 2016-08-30 00:26:14 1940 Initial revision (published)