※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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秒で2位が0.03秒5人、まあ平凡タイム。


#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
配列の値を改定しながら配列の指定された範囲のなかの最小値をこたえていく問題。
15個目のテストデータまでは通るけど、そこから先が高速化できない。

#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);
	}
}