Submission #932135


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

struct UF{
	int par[102],r[102],siz[102];
	void init(){
		rep(i,102){
			par[i] = i;
			r[i] = 0;
			siz[i] = 1;
		}
	}
	int find(int x){
		if(par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	bool same(int x,int y){
		return find(x) == find(y);
	}
	void unit(int x,int y){
		if(same(x,y))return;
		x = find(x);
		y = find(y);
		if(r[x] < r[y]){
			par[x] = y;
			siz[y] += siz[x];
		}
		else {
			par[y] = x;
			siz[x] += siz[y];
			if(r[x] == r[y]){
				r[x] ++;
			}
		}
	}
}uf;

const ll M = 1000000007;

ll modpow(ll x,ll k){
	if(k == 0)return 1;
	ll ret = modpow(x,k/2);
	ret *= ret; ret %= M;
	if(k%2 == 1){ ret *= x; ret %= M; }
	return ret;
}

ll inverse(ll x){
	return modpow(x,M-2);
}

ll C(ll n,ll k){
	ll ret = 1;
	rep1(i,k){
		ret *= n+1-i; ret %= M;
		ret *= inverse(i); ret %= M;
	}
	return ret;
}

vector<P> G[102];
int color[102];
bool dfs(int v,int c){
	if(color[v] == c)return true;
	if(color[v] == 0)return true;
	if(color[v] != -1)return false;
	color[v] = c;
	rep(i,G[v].size()){
		if(!dfs(G[v][i].fr,c))return false;;
	}
	return true;
}
bool same(int s,int t,int u){
	rep(i,102)color[i] = -1;
	color[s] = 0;
	dfs(t,1);
	return dfs(u,2);
}

int main(){
	ll n,m,k;
	ll a[102],b[102];
	scanf("%lld%lld%lld",&n,&m,&k);
	rep(i,m){
		scanf("%lld%lld",&a[i],&b[i]);
		G[a[i]].pb(P(b[i],i));
		G[b[i]].pb(P(a[i],i));
	}
	
	ll f[52],g[52];
	rep1(i,n){
		f[i] = modpow(k,i);
		rep1(d,i-1){
			if(i%d == 0)f[i] += M-f[d];
		}
		f[i] %= M;
		g[i] = 0;
		rep1(d,i){
			if(i%d == 0)g[i] += f[d]*inverse(d);
		}
		g[i] %= M;
		//cout << i << ":" << f[i] << " " << g[i] << endl;
	}
	
	uf.init();
	rep1(i,n){
		for(int j = 0 ; j < G[i].size() ; j ++){
			for(int t = j+1 ; t < G[i].size() ; t ++){
				if(!same(i,G[i][j].fr,G[i][t].fr)){
					uf.unit(G[i][j].sc,G[i][t].sc);
					//printf("%d %lld %lld\n",i,G[i][j].fr,G[i][j].sc);
					//printf("%lld %lld\n",G[i][j].sc,G[i][t].sc);
				}
			}
		}
	}
	
	/*rep(i,m){
		cout << i << ":" << uf.find(i) << endl;
	}*/
	
	ll ret = 1;
	ll used = 0;
	rep(i,m){
		if(uf.find(i) != i)continue;
		if(uf.siz[i] == 1){
			ret *= k;
			ret %= M;
			continue;
		}
		set<ll> cnt;
		rep(j,m){
			if(uf.same(i,j)){
				//cout << i << " " << j << endl;
				//cout << uf.find(i) << " " << uf.find(j) << endl;
				cnt.insert(a[j]);
				cnt.insert(b[j]);
			}
		}
		if(cnt.size() == uf.siz[i])ret *= g[cnt.size()];
		else ret *= C(k+uf.siz[i]-1,k-1);
		used += cnt.size();
		ret %= M;
		//cout << i << ":" << cnt.size() << " " << ret << endl;
	}
	//rep(i,m-used){ ret *= k; ret %= M; }
	cout << ret << endl;
}

Submission Info

Submission Time
Task F - Painting Graphs with AtCoDeer
User yokozuna57
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 3706 Byte
Status
Exec Time 4 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:116:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&m,&k);
                                ^
./Main.cpp:118:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a[i],&b[i]);
                                ^

Test Cases

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