fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define CLR(x,y) memset(x,y,sizeof(x))
  6. #define SQ(x) ((x)*(x))
  7. #define ALL(x) (x).begin(),(x).end()
  8. #define LL long long
  9.  
  10. inline LL bigmod ( LL a, LL p, LL m ) {
  11.     LL res = 1 % m, x = a % m;
  12.     while ( p ) {
  13.         if ( p & 1 ) res = ( res * x ) % m;
  14.         x = ( x * x ) % m; p >>= 1;
  15.     }
  16.     return res;
  17. }
  18.  
  19. const LL inf = 10000000000000000;
  20. const int Size = 1000055;
  21.  
  22. LL MOD[25];
  23.  
  24. int N,M,K,Q;
  25. LL B[Size];
  26. vector<int> Graph[Size];
  27. vector<int> LEVEL[25];
  28. int ID[Size];
  29. int SIZE[25];
  30.  
  31. LL DP[Size][25];
  32.  
  33. /// cur = current node
  34. /// d = distance between the current node and the node whose attractive value we are calculating.
  35.  
  36. LL call(int cur,int d){
  37.     if(DP[cur][d] != -1) return DP[cur][d];
  38.  
  39.     LL res = 0;
  40.     for(int i = 0;i<Graph[cur].size();i++){
  41.         int v = Graph[cur][i];
  42.         LL Av = call(v,d+1);
  43.         res = (res + bigmod(B[cur],Av,MOD[d]));
  44.     }
  45.  
  46.     if(Graph[cur].size() == 0) res = B[cur]%MOD[d];
  47.  
  48.     return DP[cur][d] = res%MOD[d];
  49. }
  50.  
  51. int main () {
  52.  
  53.     MOD[1] = 1000000007;
  54.     MOD[2] = 1000000006;
  55.     MOD[3] = 500000002;
  56.     MOD[4] = 243900800;
  57.     MOD[5] = 79872000;
  58.     MOD[6] = 19660800;
  59.     MOD[7] = 5242880;
  60.     MOD[8] = 2097152;
  61.     MOD[9] = 1048576;
  62.     MOD[10] = 524288;
  63.     MOD[11] = 262144;
  64.     MOD[12] = 131072;
  65.     MOD[13] = 65536;
  66.     MOD[14] = 32768;
  67.     MOD[15] = 16384;
  68.     MOD[16] = 8192;
  69.     MOD[17] = 4096;
  70.     MOD[18] = 2048;
  71.     MOD[19] = 1024;
  72.     MOD[20] = 512;
  73.  
  74.     int u,v;
  75.     scanf("%d %d %d",&N,&M,&K);
  76.     for(int i = 1;i<=N;i++){
  77.         scanf("%lld",&B[i]);
  78.     }
  79.     for(int lvl = 1;lvl<=K;lvl++){
  80.         scanf("%d",&SIZE[lvl]);
  81.         for(int i = 1;i<=SIZE[lvl];i++){
  82.             scanf("%d",&u);
  83.             LEVEL[lvl].pb(u);
  84.             ID[u] = lvl;
  85.         }
  86.     }
  87.  
  88.     for(int i = 1;i<=M;i++){
  89.         scanf("%d %d",&u,&v);
  90.         if(ID[u] < ID[v]) Graph[u].pb(v);
  91.         else Graph[v].pb(u);
  92.     }
  93.  
  94.     CLR(DP,-1);
  95.  
  96.     scanf("%d",&Q);
  97.     for(int i = 1;i<=Q;i++){
  98.         scanf("%d",&u);
  99.         LL res = call(u,1);
  100.         printf("%lld\n",res);
  101.     }
  102.     return 0;
  103. }
  104.  
Success #stdin #stdout 0.08s 222208KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/NeF7o5
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!