UVA 558 - Wormholes

#include"bits/stdc++.h"
using namespace std;
long i,flag;
#define inf (1<<29)
long dis[1005];
struct node
{
    long u,v;
    long w;
};
vector<node>vec;
void bellman_ford(long n,long m)
{
    for(i=0;i<n;i++)
    dis[i]=inf;
    dis[0]=0;//source a 0 rakhlam
    long j;
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<m;j++)
        {
            if((dis[vec[j].u]+vec[j].w<dis[vec[j].v])&&(dis[vec[j].u]!=inf))
            {
                dis[vec[j].v]=dis[vec[j].u]+vec[j].w;
            }
        }
    }
    for(j=0;j<m;j++)
    {
        if(dis[vec[j].u]+vec[j].w<dis[vec[j].v])
        {
            flag=1;
        }
    }
}
int main()
{
    //cout<<inf<<endl;
    long ts;
    cin>>ts;
    while(ts--)
    {
        long n,m,a,b,c;
        cin>>n>>m;
        node edge;
        for(i=0;i<m;i++)
        {
            cin>>a>>b>>c;
            edge.u=a;
            edge.v=b;
            edge.w=c;
            vec.push_back(edge);
        }
        flag=0;
        bellman_ford(n,m);
        if(flag==0)
        {
            printf("not possible\n");
        }
        else
            printf("possible\n");
        for(i=0;i<n+2;i++)
        {
            dis[i]=0;
        }
        vec.clear();
    }
    return 0;
}

UVA 924 Spreading the News

#include<bits/stdc++.h>
using namespace std;
vector<long>vec[2505];
long dist[2505];
long bfs(long s)
{
    memset(dist,-1,sizeof(dist));
    queue<long>q;
    q.push(s);
    dist[s]=0;
    long u,v,i1;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(i1=0;i1<vec[u].size();i1++)
        {
            v=vec[u][i1];
            if(dist[v]==-1)
            {
                dist[v]=dist[u]+1;
                q.push(v);
            }
        }
    }
}
main()
{
    long n;
    while(cin>>n)
    {
        long i,a,j,b;
        for(i=0;i<n;i++)
        {
            cin>>a;
            for(j=1;j<=a;j++)
            {
                cin>>b;
                vec[i].push_back(b);
            }
        }
        long ts,x;
        cin>>ts;
        while(ts--)
        {
            cin>>x;
            bfs(x);
            sort(dist,dist+n);
            long day,mx,cs;
            day=mx=i=0;
            for(i=0; i<n; i++)
            {
                j=i;
                cs=0;
                while(dist[i]==dist[j])
                {
                    if(dist[j]>0)
                    cs++;
                    j++;
                }
                if(cs>mx)
                {
                    mx=cs;
                    day=dist[i];
                }
                i=j-1;
            }
            if(dist[n-1]==0)
                cout<<0<<endl;
            else
                cout<<mx<<" "<<day<<endl;
        }
        for(i=0;i<n;i++)
            vec[i].clear();
    }
}

UVA 10653 - Bombs! NO they are Mines!!

#include<bits/stdc++.h>
using namespace std;
long dx[]={1,0,-1,0};
long dy[]={0,1,0,-1};
long row,col;
char s[1010][1010];
long dis[1010][1010]={0},vis[1010][1010]={0};
long bfs(long x,long y)
{
    queue< pair<long,long> >q;
    pair<long,long>pr;
    long x1,y1,i1;
    dis[x][y]=0;
    vis[x][y]=1;
    q.push(make_pair(x,y));
    while(!q.empty())
    {
        pr=q.front();
        x1=pr.first;
        y1=pr.second;
        for(i1=0;i1<4;i1++)
        {
            x1=pr.first+dx[i1];
            y1=pr.second+dy[i1];
            if((x1>=0&&x1<row)&&(y1>=0&&y1<col)&&(vis[x1][y1]==0)&&(s[x1][y1]!='#'))
            {
                dis[x1][y1]=dis[pr.first][pr.second]+1;
                q.push(make_pair(x1,y1));
                vis[x1][y1]=1;
                if(s[x1][y1]=='h')
                {
                    return dis[x1][y1];
                }
            }
        }
        q.pop();
    }
}
int main()
{
    while(cin>>row>>col)
    {
        if(row==0&&col==0)
            break;
        long n,i,j,rnumbr,pos,a;
        cin>>n;
        for(i=0;i<row;i++)
        {
            for(j=0;j<col;j++)
            {
                s[i][j]='*';
                dis[i][j]=0;
                vis[i][j]=0;
            }
        }
        for(i=1;i<=n;i++)
        {
            cin>>rnumbr;
            cin>>a;
            for(j=1;j<=a;j++)
            {
                cin>>pos;
                s[rnumbr][pos]='#';
            }
        }
        long sx,sy,ddx,ddy;
        cin>>sx>>sy>>ddx>>ddy;
        s[ddx][ddy]='h';
        cout<<bfs(sx,sy)<<endl;
    }
    return 0;
}

UVA 562 - Dividing coins

#include <bits/stdc++.h>
using namespace std;
long n,dp[110][110*500];
long coin[110],x;
long call(long i1,long wt)
{
    if(i1==n)
        return 0;
    if(dp[i1][wt]!=-1)
        return dp[i1][wt];
    long prof1=0,prof2=0;
    if((wt+coin[i1])<=x)
    {
        prof1=coin[i1]+call(i1+1,wt+coin[i1]);
    }
    else
        prof1=0;
    prof2=call(i1+1,wt);
    dp[i1][wt]=max(prof1,prof2);
    return dp[i1][wt];
}
main()
{
    long ts;
    cin>>ts;
    while(ts--)
    {
        long m,i,sum=0;
        cin>>n;
        for(i=0;i<n;i++)
           {
               cin>>coin[i];
               sum+=coin[i];
           }
        x=sum/2;
        memset(dp,-1,sizeof(dp));
        long ans=call(0,0);
        ans=sum-(ans*2);
        printf("%ld\n",ans);
    }
}

UVA 10608 - Friends

#include <bits/stdc++.h>
using namespace std;
long pr[30010];
long find(long r)
{
    if(pr[r]==r)
        return r;
    else
        return pr[r]=find(pr[r]);
}
main()
{
    long ts;
    cin>>ts;
    while(ts--)
    {
        long node,edge,i,u,v,x,y;
        cin>>node>>edge;
        for(i=1;i<=node;i++)
        {
            pr[i]=i;
        }
        for(i=1;i<=edge;i++)
        {
            cin>>u>>v;
            x=find(u);
            y=find(v);
            if(x!=y)
            {
                pr[y]=x;
            }
        }
        long mx=0,ar[30010]={0};
        for(i=1;i<=node;i++)
        {
            x=find(i);
            ar[x]++;
            mx=max(mx,ar[x]);
        }
        cout<<mx<<endl;
    }
}

UVA 10912 - Simple Minded Hashing

#include<bits/stdc++.h>
#define sf2(a,b) scanf("%lld%lld",&a,&b)
using namespace std;
bool vis[28][28][355];
long long dp[28][28][355];
long long l,s;
long long callkorlam(long long pos,long long len,long long tot)
{
    if(l==len)
    {
        if(tot==0)
            return 1;
        else
            return 0;
    }
    if(tot==0)
    {
        if(l==len)
            return 1;
        else
            return 0;
    }
    if(pos>26)
    {
        if(len==l&&tot==0)
        {
            return 1;
        }
        else
            return 0;
    }
    long long fst=0,scnd=0;
    if(vis[pos][len][tot]!=false)
    {
        return dp[pos][len][tot];
    }
    if(tot-pos>=0)
    {
        fst=callkorlam(pos+1,len+1,tot-pos);
    }
    scnd=callkorlam(pos+1,len,tot);
    vis[pos][len][tot]=true;
    return dp[pos][len][tot]=fst+scnd;
}
main()
{
    long long cs=1;
    while(cin>>l>>s)
    {
        long long rs=0;
        if(l==0&&s==0)
            break;
        memset(vis,false,sizeof(vis));
        if(l>26 || s>351)
        {
            rs=0;
        }
        else
        {
            rs=callkorlam(1,0,s);
        }
            printf("Case %lld: %lld\n",cs++,rs);
    }
}

UVA 10006 - Carmichael Numbers

#include<bits/stdc++.h>
#define sz 65100
using namespace std;
long status[65100];
void sieve()
{
    long long i,j;
    status[1]=1,status[0]=1;
    for(i=3;i<=sz;i++)
    {
        if(status[i]==0)
        {
            for(j=i*i;j<=sz;j+=i)
            {
                status[j]=1;
            }
        }
    }
}
long long bigmod(long long base,long long power,long long mod)
{
    long long ret=1;
    while(power)
    {
        if(power & 1)
            ret=(ret*base)%mod;
        base = (base*base)%mod;
        power=power>>1;
    }
    return ret;
}
main()
{
    sieve();
    long long n;
    while(cin>>n)
    {
        long long i1,xx,f=0;
        if(n==0)
            break;
        else
        {
            if(status[n]==0)
            {
                printf("%lld is normal.\n",n);
            }
            else
            {
                for(i1=2;i1<n;i1++)
                {
                    xx=bigmod(i1,n,n);
                    if(xx!=i1)
                    {
                        f=1;
                        break;
                    }
                }
               // cout<<f<<endl;
                if(f==0)
                {
                    printf("The number %lld is a Carmichael number.\n",n);
                }
                else
                {
                    printf("%lld is normal.\n",n);
                }
            }
        }
    }
}

UVA 

UVA 793 - Network Connections

#include<bits/stdc++.h>
using namespace std;
long par[1000005];
long find_korlam(long a1)
{
    if(par[a1]==a1)
        return a1;
    else
        find_korlam(par[a1]);
}
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        long n,i;
        cin>>n;
        for(i=1;i<=n;i++)
            par[i]=i;
        char s;
        long a,b,u,v,success=0,unsuccess=0;
        getchar();
        while((s=getchar())&&(isalpha(s)))
        {
            cin>>a>>b;
            getchar();
            u=find_korlam(a);
            v=find_korlam(b);
            if(s=='c')
            {
                if(u!=v)
                    par[u]=v;
            }
            else if(s=='q')
            {
                if(u==v)
                {
                    success++;
                }
                else
                    unsuccess++;
            }
            else
                break;
        }
        if(cs>1)
            cout<<endl;
        cs++;
        cout<<success<<","<<unsuccess<<endl;
    }
}

UVA 11991 - Easy Problem from Rujia Liu?

#include<bits/stdc++.h>
using namespace std;
vector<long>vec[1000010];
main()
{
    long n,m;
    while(cin>>n>>m)
    {
        long i,a,b;
        for(i=1;i<=n;i++)
        {
            cin>>a;
            vec[a].push_back(i);
        }
        for(i=1;i<=m;i++)
        {
            cin>>a>>b;
           if(vec[b].size()<a)
                cout<<0<<endl;
            else
                cout<<vec[b][a-1]<<endl;
        }
        for(i=0;i<=1000000;i++)
        {
            vec[i].clear();
        }
    }
}

UVA 13148 - A Giveaway

#include <bits/stdc++.h>
using namespace std;
main()
{
    double n;
    while(cin>>n)
    {
        if(n==0)
            break;
        double ans = round(pow(n, 1./3.));
        double ans1=ans*ans*ans;
        if(ans1==n)
        {
            printf("Special\n");
        }
        else
            printf("Ordinary\n");
    }
}

OR

#include <bits/stdc++.h>
using namespace std;
main()
{
    long n;
    while(cin>>n)
    {
        if(n==0)
            break;
        double ans = round(pow(n, 1./3.));
        long ans1=ans*ans*ans;
        if(ans1==n)
        {
            printf("Special\n");
        }
        else
            printf("Ordinary\n");
    }
}

How can I obtain the cube root in C++?

ans = round(pow(n, 1./3.));