結果
問題 | No.1207 グラフX |
ユーザー |
![]() |
提出日時 | 2020-08-30 13:05:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 11,368 bytes |
コンパイル時間 | 3,538 ms |
コンパイル使用メモリ | 215,160 KB |
最終ジャッジ日時 | 2025-01-13 20:52:55 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;#define MD (1000000007U)void *wmem;char memarr[96000000];template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );(*arr)=(T*)(*mem);(*mem)=((*arr)+x);}struct Modint{unsigned val;Modint(){val=0;}Modint(int a){val = ord(a);}Modint(unsigned a){val = ord(a);}Modint(long long a){val = ord(a);}Modint(unsigned long long a){val = ord(a);}inline unsigned ord(unsigned a){return a%MD;}inline unsigned ord(int a){a %= (int)MD;if(a < 0){a += MD;}return a;}inline unsigned ord(unsigned long long a){return a%MD;}inline unsigned ord(long long a){a %= (int)MD;if(a < 0){a += MD;}return a;}inline unsigned get(){return val;}inline Modint &operator+=(Modint a){val += a.val;if(val >= MD){val -= MD;}return *this;}inline Modint &operator-=(Modint a){if(val < a.val){val = val + MD - a.val;}else{val -= a.val;}return *this;}inline Modint &operator*=(Modint a){val = ((unsigned long long)val*a.val)%MD;return *this;}inline Modint &operator/=(Modint a){return *this *= a.inverse();}inline Modint operator+(Modint a){return Modint(*this)+=a;}inline Modint operator-(Modint a){return Modint(*this)-=a;}inline Modint operator*(Modint a){return Modint(*this)*=a;}inline Modint operator/(Modint a){return Modint(*this)/=a;}inline Modint operator+(int a){return Modint(*this)+=Modint(a);}inline Modint operator-(int a){return Modint(*this)-=Modint(a);}inline Modint operator*(int a){return Modint(*this)*=Modint(a);}inline Modint operator/(int a){return Modint(*this)/=Modint(a);}inline Modint operator+(long long a){return Modint(*this)+=Modint(a);}inline Modint operator-(long long a){return Modint(*this)-=Modint(a);}inline Modint operator*(long long a){return Modint(*this)*=Modint(a);}inline Modint operator/(long long a){return Modint(*this)/=Modint(a);}inline Modint operator-(void){Modint res;if(val){res.val=MD-val;}else{res.val=0;}return res;}inline operator bool(void){return val!=0;}inline operator int(void){return get();}inline operator long long(void){return get();}inline Modint inverse(){int a = val;int b = MD;int u = 1;int v = 0;int t;Modint res;while(b){t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}if(u < 0){u += MD;}res.val = u;return res;}inline Modint pw(unsigned long long b){Modint a(*this);Modint res;res.val = 1;while(b){if(b&1){res *= a;}b >>= 1;a *= a;}return res;}inline bool operator==(int a){return ord(a)==val;}inline bool operator!=(int a){return ord(a)!=val;}};inline Modint operator+(int a, Modint b){return Modint(a)+=b;}inline Modint operator-(int a, Modint b){return Modint(a)-=b;}inline Modint operator*(int a, Modint b){return Modint(a)*=b;}inline Modint operator/(int a, Modint b){return Modint(a)/=b;}inline Modint operator+(long long a, Modint b){return Modint(a)+=b;}inline Modint operator-(long long a, Modint b){return Modint(a)-=b;}inline Modint operator*(long long a, Modint b){return Modint(a)*=b;}inline Modint operator/(long long a, Modint b){return Modint(a)/=b;}inline int my_getchar_unlocked(){static char buf[1048576];static int s = 1048576;static int e = 1048576;if(s == e && e == 1048576){e = fread_unlocked(buf, 1, 1048576, stdin);s = 0;}if(s == e){return EOF;}return buf[s++];}inline void rd(int &x){int k;int m=0;x=0;for(;;){k = my_getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = my_getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}struct MY_WRITER{char buf[1048576];int s;int e;MY_WRITER(){s = 0;e = 1048576;}~MY_WRITER(){if(s){fwrite_unlocked(buf, 1, s, stdout);}}};MY_WRITER MY_WRITER_VAR;void my_putchar_unlocked(int a){if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);MY_WRITER_VAR.s = 0;}MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;}inline void wt_L(char a){my_putchar_unlocked(a);}inline void wt_L(int x){int s=0;int m=0;char f[10];if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){my_putchar_unlocked('-');}while(s--){my_putchar_unlocked(f[s]+'0');}}inline void wt_L(Modint x){int i;i = (int)x;wt_L(i);}template<class T, class S> inline T pow_L(T a, S b){T res = 1;res = 1;for(;;){if(b&1){res *= a;}b >>= 1;if(b==0){break;}a *= a;}return res;}inline double pow_L(double a, double b){return pow(a,b);}template<class S> inline void arrInsert(const int k, int &sz, S a[], const S aval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}a[k] = aval;}template<class S, class T> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}for(i=sz-1;i>k;i--){b[i] = b[i-1];}a[k] = aval;b[k] = bval;}template<class S, class T, class U> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}for(i=sz-1;i>k;i--){b[i] = b[i-1];}for(i=sz-1;i>k;i--){c[i] = c[i-1];}a[k] = aval;b[k] = bval;c[k] = cval;}template<class S, class T, class U, class V> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const Ucval, V d[], const V dval){int i;sz++;for(i=sz-1;i>k;i--){a[i] = a[i-1];}for(i=sz-1;i>k;i--){b[i] = b[i-1];}for(i=sz-1;i>k;i--){c[i] = c[i-1];}for(i=sz-1;i>k;i--){d[i] = d[i-1];}a[k] = aval;b[k] = bval;c[k] = cval;d[k] = dval;}struct unionFind{int *d;int N;int M;inline void malloc(const int n){d = (int*)std::malloc(n*sizeof(int));M = n;}inline void malloc(const int n, const int fg){d = (int*)std::malloc(n*sizeof(int));M = n;if(fg){init(n);}}inline void free(void){std::free(d);}inline void walloc(const int n, void **mem=&wmem){walloc1d(&d, n, mem);M = n;}inline void walloc(const int n, const int fg, void **mem=&wmem){walloc1d(&d, n, mem);M = n;if(fg){init(n);}}inline void init(const int n){int i;N = n;for(i=(0);i<(n);i++){d[i] = -1;}}inline void init(void){init(M);}inline int get(int a){int t = a;int k;while(d[t]>=0){t=d[t];}while(d[a]>=0){k=d[a];d[a]=t;a=k;}return a;}inline int connect(int a, int b){if(d[a]>=0){a=get(a);}if(d[b]>=0){b=get(b);}if(a==b){return 0;}if(d[a] < d[b]){d[a] += d[b];d[b] = a;}else{d[b] += d[a];d[a] = b;}return 1;}inline int operator()(int a){return get(a);}inline int operator()(int a, int b){return connect(a,b);}inline int& operator[](const int a){return d[a];}inline int size(int a){a = get(a);return -d[a];}inline int sizeList(int res[]){int i;int sz=0;for(i=(0);i<(N);i++){if(d[i]<0){res[sz++] = -d[i];}}return sz;}};struct graph{int N;int *es;int **edge;void setEdge(int N__, int M, int A[], int B[], void **mem = &wmem){int i;N = N__;walloc1d(&es, N, mem);walloc1d(&edge, N, mem);for(i=(0);i<(N);i++){es[i] = 0;}for(i=(0);i<(M);i++){es[A[i]]++;es[B[i]]++;}for(i=(0);i<(N);i++){walloc1d(&edge[i], es[i], mem);}for(i=(0);i<(N);i++){es[i] = 0;}for(i=(0);i<(M);i++){edge[A[i]][es[A[i]]++] = B[i];edge[B[i]][es[B[i]]++] = A[i];}}void getDist(int root, int res[], void *mem = wmem){int i;int j;int k;int*q;int s;int z;walloc1d(&q, N, &mem);for(i=(0);i<(N);i++){res[i]=-1;}res[root]=0;s=0;z=1;q[0]=root;while(z){i=q[s++];z--;for(j=(0);j<(es[i]);j++){k=edge[i][j];if(res[k]>=0){continue;}res[k]=res[i]+1;q[s+z++]=k;}}}void SubTreeSize(int root, int res[], void *mem = wmem){int i;int j;int k;int m;int *q;int qs = 0;int qe = 1;walloc1d(&q,N,&mem);for(i=(0);i<(N);i++){res[i] = -1;}res[root] = 0;q[0] = root;while(qs < qe){i = q[qs++];for(j=(0);j<(es[i]);j++){k = edge[i][j];if(res[k]==0){continue;}res[k] = 0;q[qe++] = k;}}for(m=(N)-1;m>=(0);m--){i = q[m];res[i] = 1;for(j=(0);j<(es[i]);j++){k = edge[i][j];res[i] += res[k];}}}};int N;int M;int X;int A[200000];int B[200000];int Z[200000];graph g;int sz[200000];int dep[200000];int main(){wmem = memarr;int i;int j;int k = 0;unionFind uf;Modint res = 0;rd(N);rd(M);rd(X);{int Lj4PdHRW;for(Lj4PdHRW=(0);Lj4PdHRW<(M);Lj4PdHRW++){rd(A[Lj4PdHRW]);A[Lj4PdHRW] += (-1);rd(B[Lj4PdHRW]);B[Lj4PdHRW] += (-1);rd(Z[Lj4PdHRW]);}}uf.malloc(N, 1);for(i=(0);i<(M);i++){if(uf(A[i],B[i])){arrInsert(k, k, A, A[i], B, B[i], Z, Z[i]);}}g.setEdge(N, N-1, A, B);g.SubTreeSize(0, sz);g.getDist(0, dep);for(i=(0);i<(N-1);i++){if(dep[A[i]] < dep[B[i]]){swap(A[i], B[i]);}res += ((pow_L(Modint(X),Z[i]))) * sz[A[i]] * (N-sz[A[i]]);}wt_L(res);wt_L('\n');return 0;}// cLay varsion 20200813-1 [beta]// --- original code ---// int N, M, X, A[2d5], B[2d5], Z[2d5];// graph g;// int sz[2d5], dep[2d5];// {// int i, j, k = 0;// unionFind uf;// Modint res = 0;// rd(N,M,X,(A--,B--,Z)(M));// uf.malloc(N, 1);// rep(i,M) if(uf(A[i],B[i])) arrInsert(k, k, A, A[i], B, B[i], Z, Z[i]);//// g.setEdge(N, N-1, A, B);// g.SubTreeSize(0, sz);// g.getDist(0, dep);//// rep(i,N-1){// if(dep[A[i]] < dep[B[i]]) swap(A[i], B[i]);// res += (Modint(X) ** Z[i]) * sz[A[i]] * (N-sz[A[i]]);// }//// wt(res);// }