Submission #1651568


Source Code Expand

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define N 109
using namespace std;

int n,m,K,tot=1,fst[N],pnt[N<<1],nxt[N<<1],dad[N],d[N],eg[N];
int cbn[N<<1][N<<1],fa[N],sum[N],sz[N]; bool vis[N],bo[N];
int gcd(int x,int y){ return y?gcd(y,x%y):x; }
int ksm(int x,int y){
	int z=1; for (; y; y>>=1,x=(ll)x*x%mod) if (y&1) z=(ll)z*x%mod;
	return z;
}
void add(int x,int y){
	pnt[++tot]=y; nxt[tot]=fst[x]; fst[x]=tot;
}
int getfa(int x){ return x==fa[x]?x:fa[x]=getfa(fa[x]); }
void mrg(int x,int y){
	x=getfa(x); y=getfa(y);
	if (x==y) return;
	sz[y]+=sz[x]; sum[y]+=sum[x]; fa[x]=y;
}
void dfs(int x,int p){
	int i,y; vis[x]=1;
	for (i=fst[x]; i; i=nxt[i]) if (i^p^1){
		y=pnt[i];
		if (!vis[y]){
			dad[y]=x; d[y]=d[x]+1;
			eg[y]=i>>1; bo[i>>1]=1; sz[i>>1]=0;
			dfs(y,i);
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&K);
	int i,j,x,y;
	for (i=0; i<=m+K; i++)
		for (j=cbn[i][0]=1; j<=i; j++)
			cbn[i][j]=(cbn[i-1][j]+cbn[i-1][j-1])%mod;
	for (i=1; i<=m; i++){
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	for (i=1; i<=m; i++){
		fa[i]=i; sz[i]=sum[i]=1;
	}
	for (i=1; i<=n; i++) if (!vis[i]) dfs(i,0);
	for (i=1; i<=m; i++) if (!bo[i]){
		x=pnt[i<<1]; y=pnt[i<<1|1];
		if (d[x]<d[y]) swap(x,y);
		for (; x!=y; x=dad[x]) mrg(eg[x],i);
	}
	int ans=1;
	for (i=1; i<=m; i++) if (getfa(i)==i){
		if (sz[i]>1)
			ans=(ll)ans*cbn[sum[i]+K-1][K-1]%mod;
		else{
			for (j=1,x=0; j<=sum[i]; j++)
				x=(x+ksm(K,gcd(j,sum[i])))%mod;
			ans=(ll)ans*x%mod*ksm(sum[i],mod-2)%mod;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Submission Info

Submission Time
Task F - Painting Graphs with AtCoDeer
User lych_cys
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1602 Byte
Status AC
Exec Time 1 ms
Memory 384 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:35:26: 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:41: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

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 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
0_002.txt AC 1 ms 256 KB
1_003.txt AC 1 ms 256 KB
1_004.txt AC 1 ms 384 KB
1_005.txt AC 1 ms 384 KB
1_006.txt AC 1 ms 384 KB
1_007.txt AC 1 ms 256 KB
1_008.txt AC 1 ms 256 KB
1_009.txt AC 1 ms 256 KB
1_010.txt AC 1 ms 256 KB
1_011.txt AC 1 ms 256 KB
1_012.txt AC 1 ms 384 KB
1_013.txt AC 1 ms 384 KB
1_014.txt AC 1 ms 384 KB
1_015.txt AC 1 ms 384 KB
1_016.txt AC 1 ms 384 KB
1_017.txt AC 1 ms 384 KB
1_018.txt AC 1 ms 384 KB
1_019.txt AC 1 ms 384 KB
1_020.txt AC 1 ms 384 KB
1_021.txt AC 1 ms 384 KB
1_022.txt AC 1 ms 384 KB
1_023.txt AC 1 ms 384 KB
1_024.txt AC 1 ms 384 KB
1_025.txt AC 1 ms 384 KB
1_026.txt AC 1 ms 384 KB
1_027.txt AC 1 ms 384 KB
1_028.txt AC 1 ms 256 KB
1_029.txt AC 1 ms 256 KB
1_030.txt AC 1 ms 256 KB
1_031.txt AC 1 ms 384 KB
1_032.txt AC 1 ms 256 KB
1_033.txt AC 1 ms 256 KB
1_034.txt AC 1 ms 256 KB
1_035.txt AC 1 ms 384 KB
1_036.txt AC 1 ms 384 KB
1_037.txt AC 1 ms 384 KB
1_038.txt AC 1 ms 384 KB
1_039.txt AC 1 ms 384 KB
1_040.txt AC 1 ms 256 KB
1_041.txt AC 1 ms 256 KB
1_042.txt AC 1 ms 256 KB
1_043.txt AC 1 ms 384 KB
1_044.txt AC 1 ms 256 KB
1_045.txt AC 1 ms 384 KB
1_046.txt AC 1 ms 384 KB
1_047.txt AC 1 ms 384 KB
1_048.txt AC 1 ms 384 KB
1_049.txt AC 1 ms 384 KB
1_050.txt AC 1 ms 384 KB
1_051.txt AC 1 ms 384 KB
1_052.txt AC 1 ms 256 KB
1_053.txt AC 1 ms 256 KB
1_054.txt AC 1 ms 256 KB
1_055.txt AC 1 ms 384 KB
1_056.txt AC 1 ms 256 KB
1_057.txt AC 1 ms 256 KB
1_058.txt AC 1 ms 256 KB
1_059.txt AC 1 ms 384 KB
1_060.txt AC 1 ms 384 KB
1_061.txt AC 1 ms 384 KB
1_062.txt AC 1 ms 384 KB
1_063.txt AC 1 ms 384 KB