Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #932041

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);
}

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(i/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()];
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 2016-10-15 22:39:45+0900 F - Painting Graphs with AtCoDeer yokozuna57 C++14 (GCC 5.4.1) 0 3542 Byte WA 4 ms 256 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:107: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:109: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 0 / 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