Guest User

Untitled

a guest
Mar 23rd, 2016
221
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int,int>   II;
  4. typedef vector<int>     VI;
  5. typedef long long int   LL;
  6. #define PB push_back
  7. #define MP make_pair
  8. #define F first
  9. #define S second
  10. #define SZ(a) (int)(a.size())
  11. #define ALL(a) a.begin(),a.end()
  12. #define SET(a,b) memset(a,b,sizeof(a))
  13. bool ok;
  14. bool check(vector<string> &G, string &A,int root)
  15. {
  16.     int n = SZ(G);
  17.     vector<int> vis(n,0);
  18.     vis[root]=1;
  19.     queue<int> Q;Q.push(root);
  20.     int done=0;
  21.     while(!Q.empty())
  22.     {
  23.         int u = Q.front();Q.pop();done++;
  24.         for(int i=0;i<n;i++)
  25.             if(!vis[i] && G[u][i]==A[i])
  26.             {
  27.                 vis[i]=1;
  28.                 Q.push(i);
  29.             }  
  30.     }
  31.     return done==n;
  32. }
  33. int idx(char c)
  34. {
  35.     if(c=='R')return 0;
  36.     if(c=='G')return 1;
  37.     if(c=='B')return 2;
  38.     return -1;
  39. }
  40. void solve(int i,vector<string> &G,string &A)
  41. {
  42.     if(i==SZ(G))
  43.     {
  44.         int n = SZ(G);
  45.         int cnt[]={0,0,0};
  46.         for(int i=0;i<n;i++)
  47.             cnt[idx(A[i])]++;
  48.         int k = (n-1)/3;
  49.         char c='.';
  50.         for(int i=0;i<3;i++)
  51.             if(cnt[i]==k+1)
  52.                 c = (i?(i==1?'G':'B'):'R');
  53.         if(c=='.')return;
  54.         for(int i=0;i<3;i++)
  55.             if(i!=idx(c) && cnt[i]!=k)
  56.                 return;
  57.         for(int i=0;i<n;i++)
  58.             if(A[i]==c && check(G,A,i))
  59.                 ok=true;
  60.         return;
  61.     }
  62.     solve(i+1,G,(A[i]='R',A));
  63.     solve(i+1,G,(A[i]='G',A));
  64.     solve(i+1,G,(A[i]='B',A));
  65. }
  66. class RGBTree {
  67. public:
  68.     string exist(vector <string> G) {
  69.         ok=false;
  70.         string A(SZ(G),'.');
  71.         solve(0,G,A);
  72.         return ok?"Exist":"Does not exist";
  73.     }
  74. };
Add Comment
Please, Sign In to add comment