Submission #1873732

---

Source Code Expand

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=400100;
const int mod=1000000007;
int n,cir[maxn],f[maxn],rd[maxn],sz[maxn],tal,tci,o,cnte,now[maxn];
bool vis[maxn];
ll jie[maxn],inv[maxn];
ll ksm(ll a,int b){ll r=1;for(;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}
ll C(int a,int b){return jie[a]*inv[b]%mod*inv[a-b]%mod;}
struct edge
{
	int t;
	edge *next;
}*con[maxn],*gra[maxn];
void ins(int x,int y,edge **a)
{
	edge *p=new edge;
	p->t=y;
	p->next=a[x];
	a[x]=p;
}
void findcir(int v,int fa)
{
	vis[v]=1;
	for(edge *p=con[v];p&&!o;p=p->next)
		if(p->t!=fa)
			{if(!vis[p->t]) findcir(p->t,v);else {o=p->t;break;}}
	//cout<<"findcir:"<<v<<' '<<o<<endl;		
	if(o) cir[++tci]=v;
	else vis[v]=0;
	if(v==o) o=0;	
}
void check(int v)
{
	vis[v]=1;
	now[++tal]=v;
	for(edge *p=con[v];p;cnte++,p=p->next)
		if(!vis[p->t]) check(p->t);
}
void dfs(int v)
{
	vis[v]=1;
	for(edge *p=con[v];p;p=p->next)
		if(!vis[p->t]) f[p->t]=v,dfs(p->t);	
}
void build()
{
	for(int i=1;i<=tal;i++)
		gra[now[i]]=NULL,rd[now[i]]=0;
	gra[0]=NULL;	
	for(int i=1;i<=tal;i++)
		for(edge *p=con[now[i]];p;p=p->next)
			if(p->t<f[now[i]]) ins(now[i],p->t,gra),rd[p->t]++;
	for(int i=1;i<=tal;i++)
		if(rd[now[i]]==0) ins(0,now[i],gra);
//	cout<<"f:"<<endl;
//	for(int i=1;i<=tal;i++)
//		cout<<now[i]<<','<<f[now[i]]<<' ';
//	cout<<endl;		
//	for(int i=0;i<=tal;i++)
//		for(edge *p=gra[now[i]];p;p=p->next)
//			cout<<now[i]<<' '<<p->t<<endl;			
}
ll dp(int v,int fa)
{
	ll re=1;
	sz[v]=0;
	for(edge *p=gra[v];p;p=p->next)
		if(p->t!=fa)
		{
			ll tmp=dp(p->t,v);
			sz[v]+=sz[p->t];
			re=re*tmp%mod*C(sz[v],sz[p->t])%mod;
			//cout<<v<<' '<<p->t<<' '<<re<<' '<<sz[v]<<' '<<sz[p->t]<<endl;
		}
	sz[v]++;
	//cout<<"dp:"<<v<<' '<<re<<endl;
	return re;	
}
ll work(int v)
{
	//cout<<"work:"<<v<<endl;
	ll re=0;
	tci=tal=o=cnte=0;
	check(v);
	//cout<<"check:"<<tal<<' '<<cnte<<endl;
	if(tal*2!=cnte) return 0;
	for(int i=1;i<=tal;i++)
		vis[now[i]]=0;
	findcir(v,-1); 
//	cout<<tci<<endl;
//	for(int i=1;i<=tci;i++)
//		cout<<cir[i]<<' ';
//	cout<<endl;	
	for(int i=1;i<=tci;i++)
		dfs(cir[i]);
	for(int i=1;i<tci;i++)
		f[cir[i]]=cir[i+1];
	f[cir[tci]]=cir[1];
	build();
	re=(re+dp(0,-1))%mod;
	for(int i=2;i<=tci;i++)
		f[cir[i]]=cir[i-1];
	f[cir[1]]=cir[tci];
	build();		
	re=(re+dp(0,-1))%mod;
	return re;
}
int main()
{
	
	scanf("%d",&n);
	jie[0]=1;
	for(int i=1;i<=2*n;i++)
		jie[i]=jie[i-1]*i%mod;
	inv[2*n]=ksm(jie[2*n],mod-2);
	for(int i=2*n-1;i>=0;i--)
		inv[i]=inv[i+1]*(i+1)%mod;
	//cout<<"C:"<<C(4,2)<<endl;
	for(int i=1;i<=2*n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		ins(x,y+n,con);
		ins(y+n,x,con);
	}
//	for(int i=1;i<=2*n;i++)
//		for(edge *p=con[i];p;p=p->next)
//			cout<<i<<' '<<p->t<<endl;
	ll ans=1;int tot=0;
	for(int i=1;i<=2*n;i++)
		if(!vis[i]) 
		{
			ans=ans*work(i)%mod*C(tot+tal,tal)%mod;
			tot+=tal;
		}
	printf("%lld",ans);	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:114:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:125:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
                      ^

Judge Result