Advertisement
Guest User

Untitled

a guest
Sep 5th, 2014
201
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. using namespace std;
  5.  
  6.  
  7. class CandyCupRunningCompetition{
  8.     public:
  9.     int n,m;
  10.     vector<int> adj[4000];
  11.     vector<int> cst[4000];
  12.     long long p3[4003];
  13.     long long sol=0;
  14.     long long mod=1000000007;
  15.     int grp[4003];
  16.     int fnd(int x){
  17.         if(grp[x]!=x){
  18.             grp[x]=fnd(grp[x]);
  19.         }
  20.         return grp[x];
  21.     }
  22.     void uni(int x,int y,int ii){
  23.         int X=fnd(x);
  24.         int Y=fnd(y);
  25.         int _0=fnd(0);
  26.         int _n=fnd(n-1);
  27.         if(_0==X && _n==Y){
  28.             sol+=p3[ii];
  29.             sol%=mod;
  30.         } else if(_0==Y && _n==X){
  31.             sol+=p3[ii];
  32.             sol%=mod;
  33.         } else {
  34.             grp[X]=Y;
  35.         }
  36.     }
  37.     int findMaximum(int N, vector <int> A, vector <int> B){
  38.         m=A.size();
  39.         n=N;
  40.         p3[0]=1;
  41.         grp[0]=0;
  42.         for(int i=1;i<4000;i++){
  43.             p3[i]=(p3[i-1]*3)%mod;
  44.             grp[i]=i;
  45.         }
  46.         for(int i=m-1;i>=0;i--){
  47.             uni(A[i],B[i],i);
  48.         }
  49.         return sol;
  50.     }
  51. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement