「AOJ Problem Set from DSL 問0～問4」の編集履歴（バックアップ）一覧に戻る

AOJ Problem Set from DSL 問0～問4 - (2014/01/24 (金) 08:22:21) のソース

*Set - Disjoint Set: Union Find Tree
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A
集合をユニオン木で管理せよという問題。
コード実行速度6/26位　タイム　0.03秒。
一位が0.02秒で２位が0.03秒５人、まあ平凡タイム。


 #include<stdio.h>
 #include<map> 
 int parents[10001];
 
 int parentSearch(int p){
 	return (parents[p]=(p==parents[p]?p:parentSearch(parents[p])));
 }
 void parentUpdate(int p,int top){
 	if(p!=parents[p]){
 		parentUpdate(parents[p],top);
 	}
 	parents[p]=top;
 }
 
 void numUnion(int x,int y){
 	int topX=parentSearch(x);
 	int topY=parentSearch(y);
 	parentUpdate(topX,topY);
 } 
 
 bool isSame(int x,int y){
 	return parentSearch(x)==parentSearch(y);
 }
 
 int main(){
 	int n,q,com,x,y;
 	scanf("%d %d",&n,&q);
 	for(int i=0;i<=n;i++){
 		parents[i]=i;
  	}
 	
 	for(int i=0;i<q;i++){
 		scanf("%d %d %d",&com,&x,&y);
 		if(com==0){
 			numUnion(x,y);
  		}else{
 			printf("%s\n",isSame(x,y)?"1":"0");
 		}
 	}
 }





*Range Query - Range Minimum Query
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A&lang=jp
配列の値を改定しながら配列の指定された範囲のなかの最小値をこたえていく問題。
１５個目のテストデータまでは通るけど、そこから先が高速化できない。

 #include<stdio.h>
 #include <vector> 
 #include <algorithm>
 #include <functional>
 #include <map>
 #include <list>
 #include <set>
 
 
 const int MAX=100001;
 const int INITIAL_VALUE=2147483647;
 
 
 struct myFind{
 	int s,t,num,no; 
 };
 
 struct myUpdate{
 	int x,y,no;
 	bool operator<(const myUpdate& up)const{
 		if(y!=up.y)return y<up.y;
 		return no<up.no;
 	}
 };
 
 
 int main(){
 
 	
 	int n,q,com,x,y;
 	std::map<int,std::list<myFind> > fs;
 	std::map<int,std::set<int> > stops;
 	std::vector<myUpdate> ups;
 	std::vector<myFind> ans;
 	
 	myFind f1;
 	myUpdate u1;
 	scanf("%d %d",&n,&q);
 	int no=0,no1=0;
 	for(int i=0;i<q;i++){
 		scanf("%d %d %d",&com,&x,&y);
 		if(com==0){
 			no++;
 			u1.no=no;
 			u1.x=x;
 			u1.y=y;
 			ups.push_back(u1);
 			stops[x].insert(no);
 		}else{
 			f1.s=x;
 			f1.t=y;
 			f1.no=no1;
 			f1.num=INITIAL_VALUE;
 			fs[no].push_back(f1);
 			ans.push_back(f1);
 			no1++;
 		}
 	}
 	no++;
 
 	
  	std::sort(ups.begin(),ups.end());
 	for(int i=0;i<ups.size();i++){
 		u1=ups[i];
 		std::map<int,std::list<myFind> >::iterator it;
 		std::list<myFind>::iterator lIt;
 		std::set<int>::iterator sIt;
 		sIt=stops[u1.x].upper_bound(u1.no);
 		int stopNo;
 		if(sIt==stops[u1.x].end())stopNo=no;
 		else stopNo=(*sIt);
 		for(it=fs.lower_bound(u1.no);it!=fs.end();it++){
 			int nowNo=(*it).first;
 			if(stopNo<=nowNo)break;
 			for(lIt=(*it).second.begin();lIt!=(*it).second.end();){
 				f1=(*lIt);
 				if(f1.s<=u1.x && u1.x<=f1.t){
 					ans[f1.no].num=u1.y;
  					lIt=(*it).second.erase(lIt);
 				}else{
 					lIt++;
 				}
 			}
 		}
 	}
  	for(int i=0;i<ans.size();i++){
 		printf("%d\n",ans[i].num);
 	}
 }