Submission #1692008
Source Code Expand
#include<bits/stdc++.h> #define mo 1000000007 using namespace std; int n,m,kk,pointnum,edgenum,tim,num,top; int dfn[100010],low[100010],po[100010],p[100010],q[100010]; int vis[100010]; vector <int> des[100010]; set<int> mp[100010]; pair<int,int> st[100010]; void tarjan(int s,int pre=0) { dfn[s]=low[s]=++tim; for (int k=0;k<des[s].size();k++) if (des[s][k]!=pre) { if (!dfn[des[s][k]]) { st[++top]=make_pair(s,des[s][k]); tarjan(des[s][k],s); if (low[des[s][k]]>=dfn[s]) { num++; while (st[top]!=make_pair(s,des[s][k])) { mp[st[top].first].insert(num);mp[st[top].second].insert(num); top--; } mp[st[top].first].insert(num);mp[st[top].second].insert(num);top--; } low[s]=min(low[s],low[des[s][k]]); } else low[s]=min(low[s],dfn[des[s][k]]); } //cerr<<s<<' '<<pre<<' '<<dfn[s]<<' '<<low[s]<<endl; } long long getmi(int a,int x) { long long ans=1; while (x) { if (x&1) ans=ans*a%mo; a=(long long)a*a%mo; x>>=1; } return ans; } long long fac[100010],nifac[100010]; long long C(int n,int m){return fac[n]*nifac[m]%mo*nifac[n-m]%mo;} long long polya(int n) { long long ans=0; for (int i=1;i<=n;i++) ans=(ans+getmi(kk,__gcd(i,n)))%mo; return ans*getmi(n,mo-2)%mo; } int pp[100010],qq[100010]; int main() { //freopen("in.txt","r",stdin); scanf("%d%d%d",&n,&m,&kk); fac[0]=nifac[0]=1; for (int i=1;i<=m+kk;i++){fac[i]=fac[i-1]*i%mo;nifac[i]=getmi(fac[i],mo-2);} for (int i=1;i<=m;i++) { scanf("%d%d",&p[i],&q[i]); des[p[i]].push_back(q[i]);des[q[i]].push_back(p[i]); } for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i); for (int i=1;i<=n;i++) for (set<int>::iterator it=mp[i].begin();it!=mp[i].end();it++) pp[*it]++; for (int s=1;s<=n;s++) for (int k=0;k<des[s].size();k++) { int t=des[s][k]; for (set<int>::iterator it=mp[s].begin();it!=mp[s].end();it++) if (mp[t].count(*it)) {qq[*it]++;break;} } long long ans=1; for (int i=1;i<=num;i++) { qq[i]/=2; if (pp[i]>qq[i]) ans=ans*kk%mo; else if (pp[i]==qq[i]) ans=ans*polya(pp[i])%mo; else ans=ans*C(qq[i]+kk-1,kk-1)%mo; } cout<<ans<<endl; }
Submission Info
Submission Time | |
---|---|
Task | F - Painting Graphs with AtCoDeer |
User | yx_lu |
Language | C++14 (GCC 5.4.1) |
Score | 1300 |
Code Size | 2189 Byte |
Status | AC |
Exec Time | 6 ms |
Memory | 10624 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:58:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d",&n,&m,&kk); ^ ./Main.cpp:63:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&p[i],&q[i]); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1300 / 1300 | ||||
Status |
|
|
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 | 5 ms | 10496 KB |
0_001.txt | AC | 5 ms | 10624 KB |
0_002.txt | AC | 5 ms | 10496 KB |
1_003.txt | AC | 5 ms | 10496 KB |
1_004.txt | AC | 5 ms | 10496 KB |
1_005.txt | AC | 5 ms | 10496 KB |
1_006.txt | AC | 5 ms | 10496 KB |
1_007.txt | AC | 5 ms | 10496 KB |
1_008.txt | AC | 5 ms | 10496 KB |
1_009.txt | AC | 5 ms | 10496 KB |
1_010.txt | AC | 5 ms | 10496 KB |
1_011.txt | AC | 5 ms | 10496 KB |
1_012.txt | AC | 5 ms | 10496 KB |
1_013.txt | AC | 5 ms | 10496 KB |
1_014.txt | AC | 5 ms | 10496 KB |
1_015.txt | AC | 5 ms | 10496 KB |
1_016.txt | AC | 5 ms | 10496 KB |
1_017.txt | AC | 5 ms | 10496 KB |
1_018.txt | AC | 5 ms | 10496 KB |
1_019.txt | AC | 5 ms | 10496 KB |
1_020.txt | AC | 5 ms | 10496 KB |
1_021.txt | AC | 5 ms | 10496 KB |
1_022.txt | AC | 5 ms | 10496 KB |
1_023.txt | AC | 5 ms | 10496 KB |
1_024.txt | AC | 5 ms | 10496 KB |
1_025.txt | AC | 5 ms | 10496 KB |
1_026.txt | AC | 5 ms | 10496 KB |
1_027.txt | AC | 5 ms | 10496 KB |
1_028.txt | AC | 5 ms | 10496 KB |
1_029.txt | AC | 5 ms | 10496 KB |
1_030.txt | AC | 5 ms | 10496 KB |
1_031.txt | AC | 5 ms | 10496 KB |
1_032.txt | AC | 5 ms | 10496 KB |
1_033.txt | AC | 5 ms | 10496 KB |
1_034.txt | AC | 5 ms | 10496 KB |
1_035.txt | AC | 5 ms | 10496 KB |
1_036.txt | AC | 5 ms | 10496 KB |
1_037.txt | AC | 5 ms | 10496 KB |
1_038.txt | AC | 5 ms | 10496 KB |
1_039.txt | AC | 5 ms | 10496 KB |
1_040.txt | AC | 5 ms | 10496 KB |
1_041.txt | AC | 5 ms | 10496 KB |
1_042.txt | AC | 5 ms | 10496 KB |
1_043.txt | AC | 5 ms | 10496 KB |
1_044.txt | AC | 5 ms | 10496 KB |
1_045.txt | AC | 5 ms | 10496 KB |
1_046.txt | AC | 5 ms | 10496 KB |
1_047.txt | AC | 5 ms | 10496 KB |
1_048.txt | AC | 5 ms | 10496 KB |
1_049.txt | AC | 5 ms | 10496 KB |
1_050.txt | AC | 5 ms | 10496 KB |
1_051.txt | AC | 5 ms | 10496 KB |
1_052.txt | AC | 5 ms | 10496 KB |
1_053.txt | AC | 5 ms | 10496 KB |
1_054.txt | AC | 5 ms | 10496 KB |
1_055.txt | AC | 5 ms | 10496 KB |
1_056.txt | AC | 5 ms | 10496 KB |
1_057.txt | AC | 5 ms | 10496 KB |
1_058.txt | AC | 5 ms | 10496 KB |
1_059.txt | AC | 5 ms | 10496 KB |
1_060.txt | AC | 6 ms | 10496 KB |
1_061.txt | AC | 5 ms | 10496 KB |
1_062.txt | AC | 5 ms | 10496 KB |
1_063.txt | AC | 5 ms | 10496 KB |