Submission #932543


Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#define SIZE 200005
#define MOD 1000000007

using namespace std;
typedef long long int ll;

ll inv[SIZE],fac[SIZE],finv[SIZE];
void make()
{
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for(int i=2;i<SIZE;i++)
	{
		inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
		fac[i]=fac[i-1]*(ll) i%MOD;
		finv[i]=finv[i-1]*inv[i]%MOD;
	}
}
ll C(int a,int b)
{
	if(a<b) return 0;
	return fac[a]*(finv[b]*finv[a-b]%MOD)%MOD;
}
int gcd(int x,int y)
{
	if(x==0) return y;
	return gcd(y%x,x);
}
ll mpow(ll m,ll t)
{
	if(t==0) return 1;
	ll ret=mpow(m*m%MOD,t/2);
	if(t%2==1) ret=ret*m%MOD;
	return ret;
}
struct UF
{
	int par[SIZE],rank[SIZE];
	
	void init(int n)
	{
		for(int i=0;i<n;i++)
		{
			par[i]=i;
			rank[i]=1;
		}
	}
	int find(int x)
	{
		if(x==par[x]) return x;
		return par[x]=find(par[x]);
	}
	void unite(int x,int y)
	{
		x=find(x);
		y=find(y);
		if(x==y) return;
		if(rank[x]<rank[y])
		{
			par[x]=y;
		}
		else
		{
			par[y]=x;
			if(rank[x]==rank[y]) rank[x]++;
		}
	}
	bool same(int x,int y)
	{
		return find(x)==find(y);
	}
};
UF uf;
vector <int> memo[SIZE];
int left[SIZE],right[SIZE];
bool now[SIZE];
struct edge
{
	int to,id;
	edge(int to=0,int id=0):to(to),id(id){}
};
vector <edge> vec[SIZE];
vector <int> can[SIZE];
int low[SIZE],ord[SIZE];
int par[SIZE],back[SIZE];
bool use[SIZE];
int now_id;
int n,m,K;

void dfs(int v,int p,int q)
{
	use[v]=true;
	par[v]=p;
	back[v]=q;
	low[v]=ord[v]=now_id++;
	for(int i=0;i<vec[v].size();i++)
	{
		edge e=vec[v][i];
		if(e.to!=p)
		{
			if(!use[e.to])
			{
				dfs(e.to,v,e.id);
				low[v]=min(low[v],low[e.to]);
			}
			else
			{
				low[v]=min(low[v],ord[e.to]);
			}
		}
	}
}
void build()
{
	for(int i=0;i<n;i++)
	{
		if(!use[i])
		{
			dfs(i,-1,-1);
		}
	}
	for(int i=0;i<n;i++)
	{
		if(par[i]==-1) continue;
		for(int j=0;j<vec[i].size();j++)
		{
			edge e=vec[i][j];
			if(e.to!=par[i]&&low[e.to]<=ord[par[i]])
			{
				can[back[i]].push_back(e.id);
				can[e.id].push_back(back[i]);
				//printf("* %d %d\n",back[i],e.id);
			}
		}
	}
}
int main()
{
	make();
	scanf("%d %d %d",&n,&m,&K);
	for(int i=0;i<m;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);a--;b--;
		vec[a].push_back(edge(b,i));
		vec[b].push_back(edge(a,i));
		left[i]=a,right[i]=b;
	}
	build();
	uf.init(m+2);
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<can[i].size();j++)
		{
			uf.unite(i,can[i][j]);
		}
	}
	for(int i=0;i<m;i++) memo[uf.find(i)].push_back(i);
	ll ret=1;
	for(int i=0;i<m;i++)
	{
		if(memo[i].size()==0) continue;
		int nd=0,cnt=memo[i].size();
		for(int j=0;j<memo[i].size();j++)
		{
			int p=memo[i][j];
			if(!now[left[p]]) nd++;
			if(!now[right[p]]) nd++;
			now[left[p]]=now[right[p]]=true;
		}
		for(int j=0;j<memo[i].size();j++)
		{
			int p=memo[i][j];
			now[left[p]]=now[right[p]]=false;
		}
		//printf("%d %d\n",nd,cnt);
		if(cnt==1) ret=ret*(ll) K%MOD;
		else
		{
			if(nd<cnt)
			{
				ret=ret*C(cnt+K-1,K-1)%MOD;
			}
			else
			{
				ll all=0;
				for(int j=1;j<=nd;j++)
				{
					all+=mpow(K,gcd(j,nd));
					if(all>=MOD) all-=MOD;
				}
				all=all*inv[nd]%MOD;
				ret=ret*all%MOD;
			}
		}
	}
	printf("%lld\n",ret);
	return 0;
}

Submission Info

Submission Time
Task F - Painting Graphs with AtCoDeer
User yutaka1999
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 3378 Byte
Status AC
Exec Time 32 ms
Memory 19200 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:146:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&K);
                            ^
./Main.cpp:150:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a,&b);a--;b--;
                       ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 64
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt
Case Name Status Exec Time Memory
0_000.txt AC 24 ms 19072 KB
0_001.txt AC 24 ms 19072 KB
0_002.txt AC 24 ms 19072 KB
1_003.txt AC 24 ms 19072 KB
1_004.txt AC 24 ms 19072 KB
1_005.txt AC 24 ms 19072 KB
1_006.txt AC 24 ms 19072 KB
1_007.txt AC 32 ms 19072 KB
1_008.txt AC 24 ms 19072 KB
1_009.txt AC 24 ms 19072 KB
1_010.txt AC 24 ms 19072 KB
1_011.txt AC 24 ms 19072 KB
1_012.txt AC 25 ms 19072 KB
1_013.txt AC 25 ms 19200 KB
1_014.txt AC 24 ms 19072 KB
1_015.txt AC 25 ms 19072 KB
1_016.txt AC 24 ms 19072 KB
1_017.txt AC 24 ms 19072 KB
1_018.txt AC 24 ms 19072 KB
1_019.txt AC 24 ms 19072 KB
1_020.txt AC 24 ms 19072 KB
1_021.txt AC 25 ms 19072 KB
1_022.txt AC 24 ms 19072 KB
1_023.txt AC 24 ms 19072 KB
1_024.txt AC 24 ms 19072 KB
1_025.txt AC 24 ms 19072 KB
1_026.txt AC 24 ms 19072 KB
1_027.txt AC 24 ms 19072 KB
1_028.txt AC 24 ms 19072 KB
1_029.txt AC 24 ms 19072 KB
1_030.txt AC 24 ms 19072 KB
1_031.txt AC 24 ms 19072 KB
1_032.txt AC 25 ms 19072 KB
1_033.txt AC 24 ms 19072 KB
1_034.txt AC 25 ms 19072 KB
1_035.txt AC 24 ms 19072 KB
1_036.txt AC 24 ms 19072 KB
1_037.txt AC 24 ms 19072 KB
1_038.txt AC 24 ms 19072 KB
1_039.txt AC 24 ms 19072 KB
1_040.txt AC 24 ms 19072 KB
1_041.txt AC 24 ms 19072 KB
1_042.txt AC 24 ms 19072 KB
1_043.txt AC 24 ms 19072 KB
1_044.txt AC 24 ms 19072 KB
1_045.txt AC 24 ms 19072 KB
1_046.txt AC 25 ms 19072 KB
1_047.txt AC 24 ms 19072 KB
1_048.txt AC 24 ms 19072 KB
1_049.txt AC 24 ms 19072 KB
1_050.txt AC 24 ms 19072 KB
1_051.txt AC 24 ms 19072 KB
1_052.txt AC 24 ms 19072 KB
1_053.txt AC 24 ms 19072 KB
1_054.txt AC 24 ms 19072 KB
1_055.txt AC 24 ms 19072 KB
1_056.txt AC 24 ms 19072 KB
1_057.txt AC 24 ms 19072 KB
1_058.txt AC 24 ms 19072 KB
1_059.txt AC 24 ms 19072 KB
1_060.txt AC 24 ms 19072 KB
1_061.txt AC 25 ms 19072 KB
1_062.txt AC 25 ms 19072 KB
1_063.txt AC 24 ms 19072 KB