Submission #19437854


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long LL;
const int N=2e5+5,md=1e9+7;
int n,head[N],cnt,ce,ans,fa[N],dep[N],fac[N],iv[N],inv[N];
bool vis[N];
vector<int>st,cir;
struct edge{
	int to,nxt;
}e[N<<1];
inline int pow(int a,int b){
	int res=1;
	for(;b;b>>=1,a=(LL)a*a%md)if(b&1)res=(LL)res*a%md;
	return res;
}
void dfs(int u){
	st.push_back(u);
	vis[u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		++ce;
		if(!vis[e[i].to])dfs(e[i].to);
	}
}
void findC(int u,int p){
	for(int i=head[u];i;i=e[i].nxt)if(e[i].to!=p){
		if(!dep[e[i].to])dep[e[i].to]=dep[u]+1,fa[e[i].to]=u,findC(e[i].to,u);
		else if(dep[e[i].to]<dep[u]){
			for(int v=u;v!=e[i].to;v=fa[v])cir.push_back(v);
			cir.push_back(e[i].to);
		}
	}
}
vector<int>G[N];
int rec[N],deg[N],sz[N];
bool tg[N];
void setpath(int u,int p){
	for(int i=head[u];i;i=e[i].nxt)if(e[i].to!=p&&!tg[e[i].to])
	rec[e[i].to]=u,setpath(e[i].to,u);
}
void DFS(int u,int p){
	sz[u]=1;
	for(int to:G[u])if(to!=p)
	DFS(to,u),sz[u]+=sz[to];
}
int getval(){
	int res=fac[sz[0]-1];
	for(int x:st)res=(LL)res*inv[sz[x]]%md;
	return res;
}
int work(){
	int res=0;
	cir.clear();
	dep[st[0]]=1;
	findC(st[0],0);
	for(int x:st)fa[x]=0;
	for(int x:cir)tg[x]=1;
	for(int x:cir)setpath(x,0);
	for(int i=0,ed=(int)cir.size();i<ed;++i)
	rec[cir[i]]=cir[(i+1)%ed];
	for(int x:st)if(x<rec[rec[x]])G[rec[x]].push_back(x),++deg[x];
	for(int x:st)if(!deg[x])G[0].push_back(x);
	DFS(0,0);
	res+=getval();
	for(int x:st)G[x].clear(),deg[x]=0;
	G[0].clear();
	reverse(cir.begin(),cir.end());
	for(int i=0,ed=(int)cir.size();i<ed;++i)
	rec[cir[i]]=cir[(i+1)%ed];
	for(int x:st)if(x<rec[rec[x]])G[rec[x]].push_back(x),++deg[x];
	for(int x:st)if(!deg[x])G[0].push_back(x);
	DFS(0,0);
	res+=getval();
	for(int x:st)G[x].clear(),deg[x]=0;
	G[0].clear();
	return res%md;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=*fac=1;i<=2*n+1;++i)fac[i]=(LL)fac[i-1]*i%md;
	iv[2*n+1]=pow(fac[2*n+1],md-2);
	for(int i=2*n;~i;--i)iv[i]=(i+1LL)*iv[i+1]%md;
	for(int i=1;i<=2*n+1;++i)inv[i]=(LL)iv[i]*fac[i-1]%md;
	for(int i=1;i<=2*n;++i){
		int u,v;
		cin>>u>>v,v+=n;
		e[++cnt]=(edge){v,head[u]},head[u]=cnt;
		e[++cnt]=(edge){u,head[v]},head[v]=cnt;
	}
	ans=fac[2*n];
	for(int i=1;i<=n;++i)if(!vis[i]){
		st.clear();
		ce=0;
		dfs(i);
		if(ce!=(int)st.size()*2)cout<<"0\n",exit(0);
		ans=(LL)ans*work()%md*iv[st.size()]%md;
	}
	cout<<ans<<'\n';
	return 0;
}

Submission Info

Submission Time
Task F - Collecting Balls
User Mrsrz
Language C++ (GCC 9.2.1)
Score 1200
Code Size 2540 Byte
Status AC
Exec Time 142 ms
Memory 27956 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 5
AC × 17
Set Name Test Cases
Sample subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt
Case Name Status Exec Time Memory
01.txt AC 136 ms 27072 KB
02.txt AC 134 ms 27956 KB
03.txt AC 124 ms 25084 KB
04.txt AC 128 ms 25480 KB
05.txt AC 142 ms 25416 KB
06.txt AC 63 ms 17880 KB
07.txt AC 128 ms 24748 KB
08.txt AC 131 ms 23576 KB
09.txt AC 130 ms 25168 KB
10.txt AC 69 ms 17884 KB
11.txt AC 58 ms 17972 KB
12.txt AC 69 ms 17892 KB
subtask0_0.txt AC 12 ms 8332 KB
subtask0_1.txt AC 13 ms 8200 KB
subtask0_2.txt AC 7 ms 8352 KB
subtask0_3.txt AC 7 ms 8272 KB
subtask0_4.txt AC 9 ms 8180 KB