백준 15745 : Snow Boots

문제 링크

또다른 USACO문제다.

눈이 쌓인 길이 있고, 각각의 신발에 대해서 최대 견딜 수 있는 눈 깊이와, 최대 보폭이 주어질 때, 각각의 신발에 대해서 이 눈길을 걸어갈 수 있는지 판별하는 문제였다.

문제를 간단히 해보면 각 신발에 대해서 눈의 높이가 신발이 견딜 수 있는 눈 깊이보다 큰 타일이 연속해서 최대 보폭이상개 있으면 눈길을 건너는 것은 불가능하므로 그것을 판단하는 문제였다.

Brute하게 풀면 각 쿼리에 대해서 전체 배열을 한번 순회해주면 해결할 수 있지만, 이는 O(n^2)로, n이 10만인 이 문제에서는 시간초과를 받을것이었다.

오프라인 쿼리와 Union-Find를 이용하여 해결하였다.

최대 견딜 수 있는 눈 깊이가 a인 신발을 사용했을 때 가지 못했던 곳은 a보다 작은 신발을 사용했을 때 마찬가지로 갈 수 없으므로, 신발을 최대 견딜 수 있는 눈 깊이로 큰 순으로 정렬해 준 다음 해결하였다.

갈 수 없는 타일은 눈의 양을 정렬한 후 이분탐색을 통해 찾았고, 갈 수 없음을 표시할 때, 양옆의 타일이 이미 갈수 없는 타일이면 union을 해줌으로써 연속되는 타일의 개수를 세었다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <utility>

using namespace std;

typedef pair<int,int> pii;

const int INF = 987654321;

int n,b;
vector<int> snow;
vector<pii> snowpii;
vector<pii> shoes;
vector<pair<pii,int>> shoespii;
vector<bool> ans;
vector<bool> valid;
vector<int> p;

int maxlen = 1;

int find(int a)
{
	if(p[a] < 0) return a;
	else return p[a] = find(p[a]);
}

int merge(int u,int v)
{
	u = find(u);
	v = find(v);

	
	if(u == v) return -1;
	
	p[v] += p[u];
	p[u] = v;
	
	return -p[v];	
}

int main(int argc, char** argv) {
	scanf("%d %d",&n,&b);
	
	p = vector<int>(n,-1);
	ans = vector<bool>(b,false);
	valid = vector<bool>(n,true);
	for(int i = 0;i<n;i++)
	{
		int s;
		scanf("%d",&s);
		
		snow.push_back(s);
		snowpii.push_back({s,i});
	}
	
	for(int i = 0;i<b;i++)
	{
		int s,d;
		scanf("%d %d",&s,&d);
		
		shoes.push_back({s,d});
		shoespii.push_back({make_pair(s,d),i});
	}
	
	sort(snowpii.begin(),snowpii.end());
	sort(shoespii.begin(),shoespii.end(),greater<pair<pii,int>>());

	for(int i = 0;i<b;i++)
	{		
		int s = shoespii[i].first.first;
		int d = shoespii[i].first.second;
	
		auto it = upper_bound(snowpii.begin(),snowpii.end(),make_pair(s,INF));
		
		if(it == snowpii.end())
		{
			ans[shoespii[i].second] = true;		
		}
		else
		{
			for(;it != snowpii.end();it++)
			{
				if(!valid[it->second]) break;
				
				valid[it->second] = false;
				
			if((it->second) + 1 < n && !valid[(it->second) + 1])
				 maxlen = max(maxlen,merge((it->second) + 1,(it->second)));
				if((it->second) - 1 >= 0 && !valid[(it->second) - 1])
 		 		 maxlen = max(maxlen,merge((it->second) - 1,(it->second)));
			}
			
			if(maxlen < d) ans[shoespii[i].second] = true;
		}		
	}
	
	for(int i = 0;i<b;i++)
	{
		printf("%d\n",ans[i]? 1 : 0);
	}
	
	return 0;
}
​