UVa 12086:Potentiometers

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;



int POT[200005],tree[524300],record[524300];

void initialize(int begin,int end,int node)
{
    if(begin==end){tree[node]=POT[begin];record[begin]=node;}


    else { int mid=(begin+end)/2;

                initialize(begin,mid,2*node);
                initialize(mid+1,end,2*node+1);
                tree[node]=tree[2*node]+tree[2*node+1];


               }
}

long long int query(int i,int j,int begin,int end,int node)
{
    int p1,p2;

    if(end<i || j<begin)return 0;

    if(i<=begin && end<=j)return tree[node];

    else {int mid=(begin+end)/2;
             p1=query(i,j,begin,mid,2*node);
              p2=query(i,j,mid+1,end,2*node+1);
              return p1+p2;
                }
}

void update(int index,int val,int begin,int end,int node)
{
   int n=record[index];
   tree[n]=val;
   n/=2;
   while(n>0)
     {
         tree[n]=tree[2*n]+tree[2*n+1];
         n/=2;
     }
}
int main()
{
    int pot,t=1;
  bool blank=false;
    while(scanf("%d",&pot)==1)
    {if(!pot)break;
        int i;

        for(i=0;i<pot;i++)
          scanf("%d",&POT[i]);
       if(blank)printf("\n");
       char command[5];
       //getchar();

       initialize(0,pot-1,1);

      /* for(i=1;i<50;i++)
       {
           cout<<"NODE "<<i<<" i"<<tree[i]<<endl;
       }*/
      // cout<<"hoise"<<endl;
      printf("Case %d:\n",t);
      t++;


       while(true)
 {
     scanf("%s",&command);
     if(strcmp("END",command)==0)break;
     else if(strcmp(command,"M")==0){int a,b;
                                                               scanf("%d%d",&a,&b);
                                                                if(a>b)swap(a,b);


                                                              printf("%d\n",query(a-1,b-1,0,pot-1,1));
                                                                //getchar();
                                                                }

      else if(strcmp(command,"S")==0){int val,index;
                                                               scanf("%d%d",&index,&val);
                                                                update(index-1,val,0,pot-1,1);
                                                                 }
     //else if(command=="S")
 }
    if(blank==false)blank=true;
    }

}

UVa 10004:Bicoloring

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>

using namespace std;


int node,edge;

bool bfs()
{

    vector<int>adjlist[1000];

    int i;
    for(i=0;i<edge;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        adjlist[x].push_back(y);
        adjlist[y].push_back(x);

    }

    queue<int>BFS;

    int colour[1000],cur=1;  //1=white,-1=black
    bool visited[1000];


    memset(visited,false,sizeof(visited));

    BFS.push(0);
    visited[0]=true;
    colour[0]=1;



    while(!BFS.empty())
    { int f=BFS.front();
      //cout<<f<<"curnode"<<endl;
        cur*=-1;
        for(i=0;i<adjlist[f].size();i++)
          {  int C=adjlist[f][i];
          //cout<<C<<"child"<<endl;
              if(visited[C]==true){
                                               if(colour[C]==colour[f])return false;
                                               }
              else { visited[C]=true;
              BFS.push(C);
                       colour[C]=colour[f]*-1;

              }

          }

          BFS.pop();

    }
    return true;
    }

int main()
{

    while(cin>>node)
    {
        if(node==0)break;


        cin>>edge;

        bool bicolour=bfs();
        if(bicolour)cout<<"BICOLORABLE."<<endl;
        else cout<<"NOT BICOLORABLE."<<endl;
    }
}

UVa-336::A Node Too Far

#include<cstdio>
#include<iostream>
#include<map>
#include<queue>
#include<cstring>
using namespace std;


int main()
{ int T=0;
    while(true){
                        int edge;
                        cin>>edge;
                        if(edge==0)break;
                        map<int,int>graph;
                        int a,b,i,j,tot=1;

                        vector<int>adjlist[110];



                        while(edge--){cin>>a>>b;
                                                if(graph[a]==0){graph[a]=tot++;
                                                          //cout<<tot<<"TOT"<<endl;
                                                                           }
                                                if(graph[b]==0){graph[b]=tot++;
                                                           //cout<<tot<<"TOT"<<endl;
                                                                        }
                                                int p=graph[a],q=graph[b];
                                                //          cout<<p<<" "<<q<<endl;
                                                adjlist[p].push_back(q);
                                                adjlist[q].push_back(p);


                                               }
                            //map<int,int>::iterator it;
                                //for(it=graph.begin();it!=graph.end();it++)cout<<(*it).first<<" "<<(*it).second<<endl;
                            /*for(i=1;i<tot;i++)
                                            {
                                                cout<<i<<" contains "<<(int)adjlist[i].size()<<" nodes"<<endl;
                                            }
*/
/*BFS*/

                            int source,ttl;
                            while(cin>>source>>ttl )
                                            {
                                            if(source+ttl==0)break;

                                            bool visited[1010];
                                            int distance[1010];
                                            queue<int>BFS;

                                            memset(visited,false,sizeof(visited));
                                            memset(distance,-1,sizeof(visited));


                                            distance[graph[ source]  ]=0;
                                            visited[graph[source]]=true;
                                            BFS.push(graph[source]);
                                            while(!BFS.empty())
                                                        {
                                                             int f=BFS.front();
                                                             // cout<<"F "<<f<<endl;
                                                              for(int i=0;i<adjlist[f].size();i++)
                                                                        { int v=adjlist[f][i];

                                                                            if(visited[v]==false)
                                                                                                {  //cout<<"V "<<v<<endl;
                                                                                                    distance[v]=distance[f]+1;
                                                                                                    visited[v]=true;
                                                                                                    BFS.push(v);
                                                                                                }

                                                                        }

                                                        BFS.pop();
                                                        }

int TOTAL=0;
for(int i=1;i<tot;i++)
  {
      if(distance[i]>ttl || distance[i]==-1)TOTAL++;
  }
cout<<"Case "<<++T<<": "<<TOTAL<<" nodes not reachable from node "<<source<<" with TTL = "<<ttl<<"."<<endl;
}



                        }


}

UVa-1180:Perfect Numbers

#include<cstdio>
#include<iostream>
#include<cmath>

#define MAX 1<<26

bool check(int N,int pos)
{
return   (bool) (N & (1<<pos));

}
int set(int N,int pos)
{return  N | (1<<pos);

}

using namespace std;

int bitsieve[(MAX>>5)+2];
void sieve()
{
   int i,j,n;
    n=(int) sqrt(MAX);
   for(i=3;i<=n;i+=2)
     {
         if(check(bitsieve[i>>5],i&31)==0)
         {//cout<<i<<"prime"<<endl;


           for(j=i*i;j<=MAX;j+=i<<1)
             {
                 bitsieve[j>>5]=set(bitsieve[j>>5],j&31);
             }

             }

     }

}


int main()
{
    sieve();

}