Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef pair<int,int> II;
- typedef vector<int> VI;
- typedef long long int LL;
- #define PB push_back
- #define MP make_pair
- #define F first
- #define S second
- #define SZ(a) (int)(a.size())
- #define ALL(a) a.begin(),a.end()
- #define SET(a,b) memset(a,b,sizeof(a))
- bool ok;
- bool check(vector<string> &G, string &A,int root)
- {
- int n = SZ(G);
- vector<int> vis(n,0);
- vis[root]=1;
- queue<int> Q;Q.push(root);
- int done=0;
- while(!Q.empty())
- {
- int u = Q.front();Q.pop();done++;
- for(int i=0;i<n;i++)
- if(!vis[i] && G[u][i]==A[i])
- {
- vis[i]=1;
- Q.push(i);
- }
- }
- return done==n;
- }
- int idx(char c)
- {
- if(c=='R')return 0;
- if(c=='G')return 1;
- if(c=='B')return 2;
- return -1;
- }
- void solve(int i,vector<string> &G,string &A)
- {
- if(i==SZ(G))
- {
- int n = SZ(G);
- int cnt[]={0,0,0};
- for(int i=0;i<n;i++)
- cnt[idx(A[i])]++;
- int k = (n-1)/3;
- char c='.';
- for(int i=0;i<3;i++)
- if(cnt[i]==k+1)
- c = (i?(i==1?'G':'B'):'R');
- if(c=='.')return;
- for(int i=0;i<3;i++)
- if(i!=idx(c) && cnt[i]!=k)
- return;
- for(int i=0;i<n;i++)
- if(A[i]==c && check(G,A,i))
- ok=true;
- return;
- }
- solve(i+1,G,(A[i]='R',A));
- solve(i+1,G,(A[i]='G',A));
- solve(i+1,G,(A[i]='B',A));
- }
- class RGBTree {
- public:
- string exist(vector <string> G) {
- ok=false;
- string A(SZ(G),'.');
- solve(0,G,A);
- return ok?"Exist":"Does not exist";
- }
- };
Add Comment
Please, Sign In to add comment