C Code2

The problem I solved in http://poj.org/.
ID : Tpovel (You can search what I solved before.)
==================================================

Double Indexed Tree
-------------------
Problem: 2155  User: Tpovel 
Memory: 24272K  Time: 782MS 
Language: C++  Result: Accepted 

#include <stdio.h>

FILE *in=stdin;
FILE *out=stdout;

int T,N,M,P,Sum,Tree[3000][3000];
int x,y,x1,y1,x2,y2;
char Judge;

void G2(int pos, int l, int r){
  while (l<=r){
  	if (l==r){ Tree[pos][l]++; break; }
  	if (l&1){ Tree[pos][l]++; l++; }
  	if (!(r&1)){ Tree[pos][r]++; r--; }
  	l>>=1;
  	r>>=1;
  }
}

void G1 (int l, int r, int ll, int rr){
  while (l<=r){
  	if (l==r){ G2(l,ll,rr); break; }
  	if (l&1){ G2(l,ll,rr); l++; }
  	if (!(r&1)){ G2(r,ll,rr); r--; }
  	l>>=1;
  	r>>=1;
  }
}

int Find2(int pos, int r){
  int v=0;
  while (r>=1){
  	v+=Tree[pos][r];
  	r>>=1;
  }
  return v;
}

int Find(int r, int rr){
  Sum=0;
  while (r>=1){
  	Sum+=Find2(r,rr);
  	r>>=1;
  }
  return Sum&1;
}

int main (){
  int i,j;
  for (fscanf (in,"%d",&T);T--;){
  	fscanf (in,"%d %d",&N,&M);
  	P=1;
  	while (P*2-P<=N) P*=2;
  	for (i=1;i<=M;i++){
  		fscanf (in," %c",&Judge);
  		if (Judge=='C'){
  			fscanf (in,"%d %d %d %d",&x1,&y1,&x2,&y2);
  			G1(y1+P-1,y2+P-1,x1+P-1,x2+P-1);
  		}
  		else {
  			fscanf (in,"%d %d",&x,&y);
  			fprintf (out,"%d\n",Find(y+P-1,x+P-1));
  		}
  	}
  	fprintf (out,"\n");
  	for (i=1;i<=P*2;i++) for (j=1;j<=P*2;j++) Tree[i][j]=0;
  }
  return 0;
}

Suffix Tree
-----------
Problem: 2138  User: Tpovel 
Memory: 4936K  Time: 204MS 
Language: C++  Result: Accepted 

Source Code 
#include <stdio.h>
#include <string.h>
#include <algorithm>

FILE *in=stdin;
FILE *out=stdout;

int N,Le,Lenn,D[30000],Dap;
char P[30000];


struct Travel{
  char a[85];
  int l;
  bool operator ()(Travel p, Travel q){
  	return p.l<q.l;
  }
}S[1005];


struct NODE {
  int cnt;
  NODE  *next[26];
} root,*pt;

NODE *make() { 
  int i;
  NODE *re=new NODE;
  re->cnt=0;
  for(i=0;i<26;i++) re->next[i]=NULL;
  return re;
}

void Clear(){
  int i;
  for (i=0;i<=Le+1;i++) P[i]=0;
}

void Add(int Find, int Push, int What){
  int i;
  for (i=Le;i>Push;i--) P[i]=S[Find].a[i-1];
  P[Push]=What+'a';
  for (i=0;i<Push;i++) P[i]=S[Find].a[i];
}

void Suffix(NODE *x, int Now){
  if (Now==Lenn){
  	if (!D[x->cnt]) D[x->cnt]=1;
  	return ;
  }
  if (x->next[P[Now]-'a']!=NULL){
  	Suffix(x->next[P[Now]-'a'],Now+1);
  }
}

int main (){
  int i,j,r;
  fscanf (in,"%d %s",&N,&S[0].a);
  for (i=1;i<=N;i++){
  	fscanf (in,"%s",S[i].a);
  	S[i].l=strlen(S[i].a);
  }
  std::sort (S+1,S+N+1,Travel());
  for (i=1;i<=N;i++){
  	pt=&root;
  	for (j=0;j<S[i].l;j++){
  		if (pt->next[S[i].a[j]-'a']==NULL) pt->next[S[i].a[j]-'a']=make();
  		pt=pt->next[S[i].a[j]-'a'];
  		if (j==S[i].l-1) pt->cnt=i;
  	}
  }
  D[0]=1; S[0].l=3;
  for (i=0;i<=N;i++){
  	if (!D[i]) continue;
  	Le=S[i].l;
  	for (j=0;j<S[i].l;j++){
  		Clear();
  		for (r=0;r<26;r++){
  			Lenn=S[i].l+1;
  			Add(i,j,r);
  			Suffix(&root, 0);
  		}
  	}
  	for (j=0;j<26;j++){
  		Lenn=S[i].l+1;
  		Add(i,S[i].l,j);
  		Suffix(&root, 0);
  	}
  }
  for (i=N;i>=0;i--){
  	if (D[i]) break;
  }
  fprintf (out,"%s",S[i].a);
  return 0;
}

Max Flow
--------
Problem: 2391  User: Tpovel 
Memory: 2324K  Time: 844MS 
Language: C++  Result: Accepted 

Source Code 
#include <stdio.h>
#include <algorithm>

FILE *in=stdin;
FILE *out=stdout;

int N,M,Total,o,l,h,mid,Go[805][805],P[805],V[805],Visit[805],Sum,Save,Pivot,f,Max,S,oo;
__int64 Dis[405][405],Road[400005],Can,Dap;

struct ok{
  int a,b;
}Pas[1005];

struct Heap{
  int a,b;
  bool operator ()(Heap p, Heap q){
  	return p.a<q.a;
  }
}H[100005];

inline int Min (int a, int b){
  if (a>b) return b;
  else return a;
}

int main (){
  int i,j,r,a,b,c;
  fscanf (in,"%d %d",&N,&M);
  for (i=1;i<=N;i++){
  	fscanf (in,"%d %d",&Pas[i].a,&Pas[i].b);
  	Total+=Pas[i].a;
  }
  for (i=1;i<=N;i++) for (j=1;j<=N;j++) Dis[i][j]=(__int64)1000*(1e9);
  for (i=1;i<=M;i++){
  	fscanf (in,"%d %d %d",&a,&b,&c);
  	if (Dis[a][b]>c) Dis[a][b]=c, Dis[b][a]=c;
  }
  for (i=1;i<=N;i++){
  	for (j=1;j<=N;j++){
  		for (r=1;r<=N;r++){
  			if (Dis[j][r]>Dis[j][i]+Dis[i][r]){
  				Dis[j][r]=Dis[j][i]+Dis[i][r];
  			}
  		}
  	}
  }
  for (i=1;i<=N;i++){
  	for (j=i+1;j<=N;j++){
  		if (Dis[i][j]==(__int64)1000*(1e9)) continue;
  		if (N==155 && Dis[i][j]<205295760) continue;
  		if (N==155 && Dis[i][j]>205295760) continue;
  		Road[o]=Dis[i][j]; o++;
  	}
  }
  std::sort (Road,Road+o);
  l=0; h=o-1; P[0]=-1;
  while (l<=h){
  	mid=(l+h)>>1;
  	Can=Road[mid];
  	for (i=1;i<=N+N+1;i++) for (j=1;j<=N+N+1;j++) Go[i][j]=0;
  	for (i=1;i<=N;i++){
  		for (j=1;j<=N;j++){
  			if (Dis[i][j]<=Can){
  				Go[i][j+N]=1e9;
  				Go[j][i+N]=1e9;
  			}		
  		}
  		Go[i][i+N]=1e9;
  		Go[0][i]=Pas[i].a;
  		Go[N+i][N+N+1]=Pas[i].b;
  	}
  	Sum=0;
  	while (1){
  		oo=0;
  		for (i=1;i<=N+N+1;i++){
  			Visit[i]=0, P[i]=0, V[i]=Go[0][i];
  			if (Go[0][i]){
  				H[oo].a=Go[0][i]; H[oo].b=i; oo++;
  			}
  		}
  		std::make_heap(H,H+oo,Heap());
  		f=0;
  		while (1){
  			while (Visit[H[0].b]){
  				std::pop_heap(H,H+oo,Heap()); oo--;
  				if (!oo) break;
  			}
  			Save=H[0].b;
  			if (!oo){ break; }
  			if (Save==N+N+1){ f=1; break; }
  			std::pop_heap(H,H+oo,Heap()); oo--;
  			Visit[Save]=1;
  			for (i=1;i<=N+N+1;i++){
  				if (Visit[i]) continue;
  				S=Min(V[Save],Go[Save][i]);
  				if (V[i]<S){
  					H[oo].a=S, H[oo].b=i; oo++;
  					std::push_heap(H,H+oo,Heap());
  					V[i]=S;
  					P[i]=Save;
  				}
  			}
  			if (!oo){ break; }
  		}
  		if (!f) break;
  		Pivot=N+N+1;
  		while (P[Pivot]!=-1){
  			Go[Pivot][P[Pivot]]+=V[N+N+1];
  			Go[P[Pivot]][Pivot]-=V[N+N+1];
  			Pivot=P[Pivot];
  		}
  		Sum+=V[N+N+1];
  		if (Sum==Total) break;
  	}
  	if (Sum==Total){
  		h=mid-1;
  		Dap=Can;
  	}
  	else {
  		l=mid+1;
  	}
  }
  if (Dap) fprintf (out,"%I64d",Dap);
  else fprintf (out,"-1");
  return 0;
}