Submission #1048277
Source Code Expand
#define DEB #include<bits/stdc++.h> #define REP(i,m) for(int i=0;i<(m);++i) #define REPN(i,m,in) for(int i=(in);i<(m);++i) #define ALL(t) (t).begin(),(t).end() #define CLR(a) memset((a),0,sizeof(a)) #define pb push_back #define mp make_pair #define fr first #define sc second using namespace std; #ifdef DEB #define dump(x) cerr << #x << " = " << (x) << endl #define prl cerr<<"called:"<< __LINE__<<endl #define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl #define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl #define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} #else #define dump(x) ; #define dumpR(x) ; #define dumpY(x) ; #define dumpG(x) ; #define prl ; template<class T> void debug(T a,T b){ ;} #endif template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; } template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; } typedef long long int lint; typedef pair<int,int> pi; namespace std{ template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.fr<<','<<a.sc<<')'; return out; } } //const int INF=5e8; int n,m; pi es[105]; int K; bool valid[105]; template<lint mod> struct Int_{ unsigned x; unsigned mpow(Int_ a,unsigned k){ Int_ res=1; while(k){ if(k&1) res=res*a; a=a*a; k>>=1; } return res.x; } unsigned inverse(Int_ a){ return mpow(a,mod-2); } Int_(): x(0) { } Int_(long long sig) { int sigt=sig%mod; if(sigt<0) sigt+=mod; x=sigt; } unsigned get() const { return (unsigned)x; } Int_ &operator+=(Int_ that) { if((x += that.x) >= mod) x -= mod; return *this; } Int_ &operator-=(Int_ that) { if((x += mod - that.x) >= mod) x -= mod; return *this; } Int_ &operator*=(Int_ that) { x = (unsigned long long)x * that.x % mod; return *this; } Int_ &operator=(Int_ that) { x=that.x; return *this;} Int_ &operator/=(Int_ that) { x=(unsigned long long) x * inverse(that.x)%mod; return *this;} bool operator==(Int_ that) const { return x==that.x; } bool operator!=(Int_ that) const { return x!=that.x; } Int_ operator-() const { return Int_(0)-Int_(*this);} Int_ operator+(Int_ that) const { return Int_(*this) += that; } Int_ operator-(Int_ that) const { return Int_(*this) -= that; } Int_ operator*(Int_ that) const { return Int_(*this) *= that; } Int_ operator/(Int_ that) const { return Int_(*this) /= that; } }; namespace std{ template<lint mod> ostream &operator <<(ostream& out,const Int_<mod>& a){ out<<a.get(); return out; } template<lint mod> istream &operator >>(istream& in,Int_<mod>& a){ in>>a.x; return in; } }; typedef Int_<1000000007> Int; stack<pi> cur; int low[200005],order[200005],cnt; vector<int> g[55]; vector<pi>bicon; int dfs(int v,int p){ order[v]=cnt++; low[v]=order[v]; for(auto e:g[v]){ int to=e; if(order[to]<order[v]) cur.push(mp(v,to)); if(order[to]==-1){ low[v]=min(dfs(to,v),low[v]); if(low[to]>=order[v]){ set<int> tmp; set<pi> es; while(1){ pi t=cur.top();cur.pop(); tmp.insert(t.fr);tmp.insert(t.sc); if(t.fr>t.sc){ swap(t.fr,t.sc); es.insert(t); swap(t.fr,t.sc); }else{ es.insert(t); } if(t.fr==v && t.sc==to) break; } bicon.pb(mp(tmp.size(),es.size())); } }else low[v]=min(low[v],order[to]); } return low[v]; } Int mpow(Int a,int b){ Int res=1; while(b){ if(b&1) res=a*res; a=a*a; b>>=1; } return res; } Int solve(int a){ Int res=0; REP(j,a) res+=mpow(K,__gcd(a,j)); res/=a; return res; } Int C[205][205]; int deg[55]; int main(){ REP(i,205){ C[i][0]=1; REP(j,i) C[i][j+1]=C[i-1][j+1]+C[i-1][j]; } cin>>n>>m>>K; REP(i,m){ cin>>es[i].fr>>es[i].sc,--es[i].fr,--es[i].sc,valid[i]=1; ++deg[es[i].fr]; ++deg[es[i].sc]; } Int res=1; REP(i,n) if(deg[i]==1){ REP(j,m) if(valid[j] && (es[j].fr==i || es[j].sc==i)){ valid[j]=false; --deg[es[j].fr]; --deg[es[j].sc]; res*=K; } } REP(i,m) if(valid[i]){ g[es[i].fr].pb(es[i].sc); g[es[i].sc].pb(es[i].fr); } memset(low,-1,sizeof(low)); memset(order,-1,sizeof(order)); REP(i,n) if(low[i]==-1) dfs(i,-1); for(auto S:bicon){ if(S.fr==S.sc) res*=solve(S.fr); else res*=C[S.sc+K-1][K-1]; } cout<<res<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Painting Graphs with AtCoDeer |
User | hogloid |
Language | C++14 (GCC 5.4.1) |
Score | 1300 |
Code Size | 4732 Byte |
Status | AC |
Exec Time | 5 ms |
Memory | 2048 KB |
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 | 1920 KB |
0_001.txt | AC | 5 ms | 1920 KB |
0_002.txt | AC | 5 ms | 1920 KB |
1_003.txt | AC | 5 ms | 1920 KB |
1_004.txt | AC | 5 ms | 1920 KB |
1_005.txt | AC | 5 ms | 1920 KB |
1_006.txt | AC | 5 ms | 2048 KB |
1_007.txt | AC | 5 ms | 1920 KB |
1_008.txt | AC | 4 ms | 1920 KB |
1_009.txt | AC | 5 ms | 1920 KB |
1_010.txt | AC | 4 ms | 1920 KB |
1_011.txt | AC | 5 ms | 1920 KB |
1_012.txt | AC | 4 ms | 1920 KB |
1_013.txt | AC | 5 ms | 2048 KB |
1_014.txt | AC | 5 ms | 1920 KB |
1_015.txt | AC | 5 ms | 1920 KB |
1_016.txt | AC | 4 ms | 2048 KB |
1_017.txt | AC | 5 ms | 2048 KB |
1_018.txt | AC | 5 ms | 1920 KB |
1_019.txt | AC | 5 ms | 2048 KB |
1_020.txt | AC | 5 ms | 2048 KB |
1_021.txt | AC | 4 ms | 1920 KB |
1_022.txt | AC | 5 ms | 1920 KB |
1_023.txt | AC | 4 ms | 1920 KB |
1_024.txt | AC | 5 ms | 1920 KB |
1_025.txt | AC | 4 ms | 1920 KB |
1_026.txt | AC | 5 ms | 1920 KB |
1_027.txt | AC | 5 ms | 2048 KB |
1_028.txt | AC | 5 ms | 1920 KB |
1_029.txt | AC | 4 ms | 1920 KB |
1_030.txt | AC | 5 ms | 1920 KB |
1_031.txt | AC | 5 ms | 1920 KB |
1_032.txt | AC | 5 ms | 1920 KB |
1_033.txt | AC | 5 ms | 1920 KB |
1_034.txt | AC | 5 ms | 1920 KB |
1_035.txt | AC | 5 ms | 1920 KB |
1_036.txt | AC | 5 ms | 1920 KB |
1_037.txt | AC | 5 ms | 1920 KB |
1_038.txt | AC | 5 ms | 1920 KB |
1_039.txt | AC | 5 ms | 1920 KB |
1_040.txt | AC | 5 ms | 1920 KB |
1_041.txt | AC | 5 ms | 1920 KB |
1_042.txt | AC | 5 ms | 1920 KB |
1_043.txt | AC | 5 ms | 1920 KB |
1_044.txt | AC | 4 ms | 1920 KB |
1_045.txt | AC | 5 ms | 1920 KB |
1_046.txt | AC | 5 ms | 1920 KB |
1_047.txt | AC | 5 ms | 1920 KB |
1_048.txt | AC | 4 ms | 1920 KB |
1_049.txt | AC | 5 ms | 1920 KB |
1_050.txt | AC | 4 ms | 1920 KB |
1_051.txt | AC | 5 ms | 2048 KB |
1_052.txt | AC | 5 ms | 1920 KB |
1_053.txt | AC | 5 ms | 1920 KB |
1_054.txt | AC | 5 ms | 1920 KB |
1_055.txt | AC | 4 ms | 2048 KB |
1_056.txt | AC | 5 ms | 1920 KB |
1_057.txt | AC | 4 ms | 1920 KB |
1_058.txt | AC | 5 ms | 1920 KB |
1_059.txt | AC | 4 ms | 1920 KB |
1_060.txt | AC | 5 ms | 1920 KB |
1_061.txt | AC | 4 ms | 1920 KB |
1_062.txt | AC | 5 ms | 1920 KB |
1_063.txt | AC | 5 ms | 1920 KB |