Solution of UVa 11488-Hyper Prefix Sets

See the problem UVa-11488

 

>>>This problem has been solved using "Trie". So if you don't known with "Trie", you should not try to understand this solution.<<<

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll cur, last, ss, sss, ans, mx;
string s;

struct node{
    int next[2];
    long long cnt;
}ar[10000009];

void new_trie(int cur){
    ar[cur].next[0]=-1;
    ar[cur].next[1]=-1;
    ar[cur].cnt=1;
}

int insrt(){
    ss=s.size(), cur=0;
    for(int k=0; k<ss; k++){
        int x=(int)s[k]-48;
        if(ar[cur].next[x]==-1){
            ar[cur].next[x]=last;
            new_trie(last++);
            cur=ar[cur].next[x];
        }
        else{
            cur=ar[cur].next[x];
            ar[cur].cnt++;
            mx=(k+1)*ar[cur].cnt;
            ans=max(mx, ans);
        }
    }
    sss=max(ss, sss);
}

int main(){
    long long t, n;
    cin>>t;
    while(t--){
        ans=0, mx=0, last=1, sss=0;
        new_trie(0);
        cin>>n;
        while(n--){
            cin>>s;
            insrt();
        }
        cout<<max(ans, sss)<<endl;
    }
    return 0;
}

Solution of UVa 11362-Phone List

See the problem  UVa-11362

#include<bits/stdc++.h> using namespace std; long long n, t, i, last=1, cur, k, x, fl; string s; struct node{ bool endmark; int next[11]; }r[100009]; void new_trie(int cur){ for(int zz=0; zz<10; zz++){ r[cur].next[zz]=-1; } r[cur].endmark=false; } void insrt(){ cur=0, k=s.size(); for(int z=0; z<k; z++){ x=(int)s[z]-48; if(r[cur].next[x]==-1){ r[cur].next[x]=last; new_trie(last++); cur=r[cur].next[x]; } else{ cur=r[cur].next[x]; if(r[cur].endmark==true)fl=1; if(z==k-1) fl=1; } if(fl==1) break; } r[cur].endmark=true; } int main(){ cin>>t; while(t--){ cin>>n; fl=0, last=1; new_trie(0); for(i=0; i<n; i++){ cin>>s; insrt(); } if(fl==1) cout<<"NO"<<endl; else cout<<"YES"<<endl; } return 0; }

Solution of Uva 11504-Virtual Friend

See the problem UVa-11503

#include<bits/stdc++.h>
using namespace std;

int ar[100009];
int par(int z){                // creating disjoint set
    if(ar[z]==z) return z;
    else return par(ar[z]);
}

int main()
{
    int t, i, n;
    string x, y;
    cin>>t;                    // test case
    while(t--){
        map<string, int>mp;    // for checking inserted person is new or old
        map<string, int>mpp;//indexing against person cope with the array position
        cin>>n;
        int l=0, arr[100009]={0};
        while(n--){
            cin>>x>>y;
            mp[x]++;
            mp[y]++;
            int ans=0;
            if(mp[x]==1&&mp[y]==1){   // when both person are new
                l++;
                mpp[x]=ar[l]=l;
                l++;
                mpp[y]=ar[l]=l;
                ans=arr[l]=2;
                ar[par(mpp[x])]=par(mpp[y]);
            }
            else if(mp[x]==1||mp[y]==1){     // when one person is new
                if(mp[x]==1){
                    l++;
                    mpp[x]=ar[l]=l;
                    ans=arr[par(mpp[y])] += 1;
                    ar[par(mpp[x])]=par(mpp[y]);
                }
                else{
                    l++;
                    mpp[y]=ar[l]=l;
                    ans=arr[par(mpp[y])] = (1+arr[par(mpp[x])]);
                    ar[par(mpp[x])]=par(mpp[y]);
                }
            }
            else{                             // when no one is new
             if((par(mpp[x])==mpp[y])||(par(mpp[y])==mpp[x])||(par(mpp[x])==par(mpp[y]))){
                    // if equal any person with another parent or both parents
                    ans=arr[par(mpp[x])];
                }
                else{
                    ans=arr[par(mpp[y])] += arr[par(mpp[x])];
                    ar[par(mpp[x])]=par(mpp[y]);
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

Solution of UVa 10685-Nature

View the problem UVa 10685

#include<bits/stdc++.h>
using namespace std;
int ar[5005];

int par(int z){
    if(ar[z]==z) return z;
    else return par(ar[z]);
}

int  main()
{
    int i, n, m;
    string s, ss, sss;
    while(scanf("%d%d", &n, &m)){
        if(n==0&&m==0) break;
        map<string, int>mp;
        map<int, int>mpp;
        int ans=0;
        for(i=1; i<=n; i++){
            cin>>s;
            mp[s]=i;
            ar[i]=i;
        }
        for(i=0; i<m; i++){
            cin>>ss>>sss;
            ar[par(mp[ss])]=par(mp[sss]);
        }
        for(i=1; i<=n; i++){
            ar[i]=par(i);
            mpp[ar[i]]++;
            ans=max(ans, mpp[ar[i]]);
        }
        cout<<ans<<endl;
        scanf("\n");
    }
    return 0;
}