Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #include<ext/pb_ds/assoc_container.hpp>
- #include<ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- #define bit_1(a) __builtin_popcount(a)
- #define ull unsigned long long
- #define ll long long
- #define pb push_back
- #define pf push_front
- #define mpr make_pair
- #define ins insert
- #define ff first
- #define ss second
- #define vi vector<int>
- #define vl vector<ll>
- #define vstr vector<string>
- #define si set<int>
- #define sl set<ll>
- #define li list<int>
- #define pii pair<int,int>
- #define pll pair<ll,ll>
- #define mii map<int,int>
- #define mll map<ll,ll>
- #define ma INT_MAX
- #define mi INT_MIN
- #define mod 1000000007
- #define pi 3.14159265359
- #define e 2.71828182846
- #define inf 1000000000000000LL
- #define all(x) x.begin(), x.end()
- #define lb(a,b,c) lower_bound(a,a+b,c)-a
- #define ub(a,b,c) upper_bound(a,a+b,c)-a
- #define lbv(a,c) lower_bound(all(a),c)-a.begin()
- #define ubv(a,c) upper_bound(all(a),c)-a.begin()
- #define srt1(a,b) sort(a,a+b)
- #define srt2(a,b) sort(a,a+b,greater<int>())
- #define gcd(a,b) __gcd(a,b)
- #define lcm(a,b) (a*(b/gcd(a,b)))
- #define harmonic(n) 0.57721566490153286l+log(n)
- #define mem(a, b) memset(a, b, sizeof(a))
- #define orderset1 tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
- #define orderset2 tree<int,null_type,greater<int>,rb_tree_tag,tree_order_statistics_node_update>
- ///s.lower_bound(a),s.upper_bound(a), for set
- ///nCr(x, y) = nCr(x-1, y-1) + nCr(x-1, y)
- ///factorial digit ((n * log10(n / e) +log10(2 * pi * n) /2.0));
- /// lcm(a,b)=a/gcd(a,b)*b (handle overflow)
- bool sortinrev1(const pair<int,int>&a,const pair<int,int>&b)
- {
- //return (a.first > b.first);
- if(a.first==b.first)return (a.second>b.second);
- else return (a.first > b.first);
- }
- bool sortinrev2(const pair<int,int>&a,const pair<int,int>&b)
- {
- //return (a.first > b.first);
- if(a.first==b.first)return (a.second<b.second);
- else return (a.first > b.first);
- }
- int fx[]={1,-1,0,0};
- int fy[]={0,0,1,-1};
- vi adj[30];
- int in[30];
- int out[30];
- int visited[30];
- int alphabet[30];
- void dfs(int node)
- {
- visited[node]=true;
- for(int i=0;i<adj[node].size();i++){
- int child=adj[node][i];
- if(!visited[child])dfs(child);
- }
- }
- int main()
- {
- int t,n;
- string str;
- cin>>t;
- while(t--){
- cin>>n;
- for(int i=0;i<26;i++)adj[i].clear();
- mem(in, 0);
- mem(out,0);
- mem(alphabet,0);
- mem(visited,false);
- getchar();
- while(n--){
- cin>>str;
- int len=str.size();
- adj[str[0]-'a'].pb(str[len-1]-'a');
- out[str[0]-'a']++;
- in[str[len-1]-'a']++;
- }
- bool flag=true;
- for(int i=0;i<26;i++){
- if(abs(in[i]-out[i])>1){
- flag=false;
- break;
- }
- }
- /*for(int i=0;i<26;i++)cout<<in[i]<<" ";
- cout<<endl;
- for(int i=0;i<26;i++)cout<<out[i]<<" ";
- cout<<endl;*/
- if(!flag){
- cout<<"The door cannot be opened.\n";
- continue;
- }
- for(int i=0;i<26;i++){
- if(in[i]||out[i]){
- alphabet[i]=-1;
- }
- }
- bool flag2=false;
- for(int i=0;i<26;i++){
- if(abs(in[i]-out[i])==1){
- flag2=true;
- dfs(i);
- break;
- }
- }
- bool flag4=false;
- if(!flag2){
- for(int i=0;i<26;i++){
- if(out[i]){
- flag4=true;
- dfs(i);
- break;
- }
- }
- }
- if(!flag2 && !flag4){
- cout<<"The door cannot be opened.\n";
- continue;
- }
- bool flag3=true;
- for(int i=0;i<26;i++){
- if(alphabet[i]==-1&&!visited[i]){
- flag3=false;
- break;
- }
- }
- if(flag3)cout<<"Ordering is possible.\n";
- else cout<<"The door cannot be opened.\n";
- }
- }
Add Comment
Please, Sign In to add comment