fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. ll grid[1009][1009];
  5. #define mod 1000000007
  6. vector<vector<ll> > v(2,vector<ll>(2,1));
  7. ll fibo(ll n)
  8. {
  9.     vector<vector<ll> > x(2,vector<ll>(2,1));
  10.     vector<vector<ll> > y(2,vector<ll>(2,1));
  11.     vector<vector<ll> > z(2,vector<ll>(2,0));   //temporary
  12.     ll i,j,k;
  13.     y[0][0]=v[0][0];
  14.     y[0][1]=v[0][1];
  15.     //y[0][2]=v[0][2];
  16.     y[1][0]=v[1][0];
  17.     y[1][1]=v[1][1];
  18.     //y[1][2]=v[1][2];
  19.     //y[2][0]=v[2][0];
  20.     //y[2][1]=v[2][1];
  21.     //y[2][2]=v[2][2];
  22.     for(i=0;i<2;i++)
  23.     {
  24.         for(j=0;j<2;j++)
  25.         {
  26.             x[i][j]=1;
  27.         }
  28.     }
  29.     while(n>0)
  30.     {
  31.         if(n&1)                             //x=x*y
  32.         {
  33.             for(i=0;i<2;i++)
  34.             {
  35.                 for(j=0;j<2;j++)
  36.                 {
  37.                     z[i][j]=0;
  38.                     for(k=0;k<2;k++)
  39.                     {
  40.                         z[i][j]=((z[i][j])%mod+(((x[i][k])%mod)*((y[k][j])%mod)%mod))%mod;
  41.                     }
  42.                 }
  43.             }
  44.             x[0][0]=z[0][0];
  45.             x[0][1]=z[0][1];
  46.             //x[0][2]=z[0][2];
  47.             x[1][0]=z[1][0];
  48.             x[1][1]=z[1][1];
  49.             //x[1][2]=z[1][2];
  50.             //x[2][0]=z[2][0];
  51.             //x[2][1]=z[2][1];
  52.             //x[2][2]=z[2][2];
  53.         }
  54.             for(i=0;i<2;i++)
  55.             {
  56.                 for(j=0;j<2;j++)
  57.                 {
  58.                     z[i][j]=0;
  59.                     for(k=0;k<2;k++)
  60.                     {
  61.                         z[i][j]=((z[i][j])%mod+(((y[i][k])%mod)*((y[k][j])%mod))%mod)%mod;
  62.                     }
  63.                 }
  64.             }
  65.             y[0][0]=z[0][0];
  66.             y[0][1]=z[0][1];
  67.             //y[0][2]=z[0][2];
  68.             y[1][0]=z[1][0];
  69.             y[1][1]=z[1][1];
  70.             //y[1][2]=z[1][2];
  71.             //y[2][0]=z[2][0];
  72.             //y[2][1]=z[2][1];
  73.             //y[2][2]=z[2][2];
  74.             n=n/2;
  75.     }
  76.     return x[0][0];
  77. }
  78. ll res(ll x)
  79. {
  80.     if(x==1)
  81.     {
  82.         return 1;
  83.     }
  84.     return fibo(x-2);
  85. }
  86. ll *id, cnt, *sz;
  87. void init(ll N)
  88. {
  89.     cnt = N;
  90. 	id = new ll[N+1];
  91. 	sz = new ll[N+1];
  92.     for(ll i=1; i<=N; i++)
  93.     {
  94.         id[i] = i;
  95. 	    sz[i] = 1;
  96. 	}
  97. }
  98. ll find(ll p)
  99. {
  100.     ll root = p;
  101.     while (root != id[root])
  102.         root = id[root];
  103.     while (p != root) {
  104.         ll newp = id[p];
  105.         id[p] = root;
  106.         p = newp;
  107.     }
  108.     return root;
  109. }
  110. // Replace sets containing x and y with their union.
  111. void merge(ll x, ll y)
  112. {
  113.     ll i = find(x);
  114.     ll j = find(y);
  115.     if (i == j) return;
  116.     // make smaller root point to larger one
  117.     if(sz[i]<sz[j])
  118.     {
  119.         id[i]=j;
  120.         sz[j]+=sz[i];
  121.     }
  122.     else
  123.     {
  124.         id[j]=i;
  125.         sz[i]+=sz[j];
  126.     }
  127.     cnt--;
  128. }
  129. // Are objects x and y in the same set?
  130. bool connected(ll x, ll y)
  131. {
  132.     return find(x) == find(y);
  133. }
  134. // Return the number of disjoint sets.
  135. ll count()
  136. {
  137.     return cnt;
  138. }
  139. void destroy()
  140. {
  141.     delete []id;
  142. 	delete []sz;
  143. }
  144. //////////////////////////UFDS ends.
  145. //////////////////////////MST code begins
  146. const ll MAX = 1000099;
  147. pair <long long, pair<ll, ll> > p[MAX];
  148. ll nodes,edges;
  149. long long kruskal()
  150. {
  151.     ll x, y;
  152.     long long cost, minimumCost = 0;
  153.     for(ll i = 1;i < edges;++i)
  154.     {
  155.         x = p[i].second.first;
  156.         y = p[i].second.second;
  157.         cost = p[i].first;
  158.         if(find(x) != find(y))
  159.         {
  160.             minimumCost += cost;
  161.             merge(x, y);
  162.         }
  163.     }
  164.     return minimumCost;
  165. }
  166. ll n;
  167. ll mp(ll x,ll y)
  168. {
  169.     return n*(x-1)+y;
  170. }
  171. ll x,y,wt;
  172. int main()
  173. {
  174.     ios_base::sync_with_stdio(false);
  175.     cin.tie(NULL);
  176.     cout.tie(NULL);
  177.     ll minimumCost,t,m,i,j,k1,k2,k3,k4,temp1,temp2;
  178.     v[0][0]=1;
  179.     v[0][1]=1;
  180.     v[1][0]=1;
  181.     v[1][1]=0;
  182.     cin>>n>>k1>>k2>>k3>>k4;
  183.     init(n*n+1);
  184.     ll num=1;
  185.     ll ans1=res(k1)%mod;
  186.     ll ans2=res(k2)%mod;
  187.     //cout<<ans1<<" "<<ans2<<"\n";
  188.     ll next_ans1=res(k1+1)%mod;
  189.     ll next_ans2=res(k2+1)%mod;
  190.     //cout<<next_ans1<<" "<<next_ans2<<"\n";
  191.     for(i=1;i<=n;i++)
  192.     {
  193.         for(j=1;j<n;j++)
  194.         {
  195.             temp1=mp(i,j);
  196.             temp2=mp(i,j+1);
  197.             x=temp1;
  198.             y=temp2;
  199.             wt=(ans1%mod+ans2%mod)%mod;
  200.             p[num] = make_pair(wt, make_pair(x, y));
  201.             //cout<<wt[num]<<"\n";
  202.             ll z1=(ans1%mod+next_ans1%mod)%mod;
  203.             ll z2=(ans2%mod+next_ans2%mod)%mod;
  204.             ans1=next_ans1%mod;
  205.             ans2=next_ans2%mod;
  206.             next_ans1=z1%mod;
  207.             next_ans2=z2%mod;
  208.             //cout<<ans1<<" "<<ans2<<"\n";
  209.             num++;
  210.         }
  211.     }
  212.     ans1=res(k3)%mod;
  213.     ans2=res(k4)%mod;
  214.     //cout<<ans1<<" "<<ans2<<"\n";
  215.     next_ans1=res(k3+1)%mod;
  216.     next_ans2=res(k4+1)%mod;
  217.     for(i=1;i<=n;i++)
  218.     {
  219.         for(j=1;j<n;j++)
  220.         {
  221.             temp1=mp(j,i);
  222.             temp2=mp(j+1,i);
  223.             x=temp1;
  224.             y=temp2;
  225.             wt=(ans1%mod+ans2%mod)%mod;
  226.             p[num] = make_pair(wt, make_pair(x, y));
  227.             //cout<<wt[num]<<"\n";
  228.             ll z1=(ans1%mod+next_ans1%mod)%mod;
  229.             ll z2=(ans2%mod+next_ans2%mod)%mod;
  230.             ans1=next_ans1%mod;
  231.             ans2=next_ans2%mod;
  232.             next_ans1=z1%mod;
  233.             next_ans2=z2%mod;
  234.             num++;
  235.         }
  236.     }
  237.     edges=num;
  238.     sort(p, p + edges);
  239.     minimumCost = kruskal();
  240.     cout << minimumCost << endl;
  241.     destroy();
  242.     return 0;
  243. }
  244.  
Runtime error #stdin #stdout 0.32s 49896KB
comments (?)
stdin
copy 
1000 2 2 2 2
stdout
copy 
Standard output is empty
https://ideone.com/eYcAdv
language:
C++ 4.3.2 (gcc-4.3.2)
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!