제출 #105701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105701		Pro_ktmr	물병 (JOI14_bottle)	C++14	100 / 100	2997 ms	100464 KiB

bottle

#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

int H,W,P,Q;
int grid[2000][2000];
int y[200000],x[200000];
int cost[2000][2000];
pair<int,int> parent[200000];
int depth[200000] = {};

int culD(int now){
	if(parent[now].first == -1) return 0;
	if(depth[now] != 0) return depth[now];
	return depth[now] = culD(parent[now].first) + 1;
}

pair<int,int> d[200000][30];
bool already[200000][30] = {};
pair<int,int> dub(int now, int x){
	if(now == -1) return MP(-1,0);
	if(already[now][x]) return d[now][x];
	already[now][x] = true;
	if(x == 1) return d[now][x] = MP(parent[now].first, parent[now].second);
	if(x == 0) return d[now][x] = MP(now,0);
	pair<int,int> tmp = dub(dub(now,x-1).first,x-1);
	return d[now][x] = MP(tmp.first, max(tmp.second, dub(now,x-1).second));
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << setprecision(9);

	cin >> H >> W >> P >> Q;
	for(int i=0; i<H; i++){
		string S;
		cin >> S;
		for(int j=0; j<W; j++){
			if(S[j] == '.') grid[i][j] = -1;
			else if(S[j] == '#') grid[i][j] = -2;
			cost[i][j] = INT_MAX;
		}
	}
	for(int i=0; i<P; i++){
		cin >> y[i] >> x[i];
		y[i]--; x[i]--;
		grid[y[i]][x[i]] = i;
	}

	priority_queue<pair<pair<int,int>,pair<int,int> > >  que;
	for(int i=0; i<P; i++){
		if(cost[y[i]][x[i]] != INT_MAX) continue;
		cost[y[i]][x[i]] = 0;
		parent[i] = MP(-1,0);
		que.push(MP(MP(0,i),MP(y[i],x[i])));
		while(!que.empty()){
			int c = -que.top().first.first;
			int par = que.top().first.second;
			int nowY = que.top().second.first;
			int nowX = que.top().second.second;
			que.pop();
			if(cost[nowY][nowX] < c) continue;
			if(nowY-1 >= 0 && cost[nowY-1][nowX] > c+1 && grid[nowY-1][nowX] >= -1){
				cost[nowY-1][nowX] = c+1;
				if(grid[nowY-1][nowX] >= 0){
					cost[nowY-1][nowX] = 0;
					parent[grid[nowY-1][nowX]] = MP(par,c);
					que.push(MP(MP(0,grid[nowY-1][nowX]),MP(nowY-1,nowX)));
					que.push(MP(MP(-c,par),MP(nowY,nowX)));
					continue;
				}
				else{
					que.push(MP(MP(-c-1,par),MP(nowY-1,nowX)));
				}
			}
			if(nowY+1 < H && cost[nowY+1][nowX] > c+1 && grid[nowY+1][nowX] >= -1){
				cost[nowY+1][nowX] = c+1;
				if(grid[nowY+1][nowX] >= 0){
					cost[nowY+1][nowX] = 0;
					parent[grid[nowY+1][nowX]] = MP(par,c);
					que.push(MP(MP(0,grid[nowY+1][nowX]),MP(nowY+1,nowX)));
					que.push(MP(MP(-c,par),MP(nowY,nowX)));
					continue;
				}
				else{
					que.push(MP(MP(-c-1,par),MP(nowY+1,nowX)));
				}
			}
			if(nowX-1 >= 0 && cost[nowY][nowX-1] > c+1 && grid[nowY][nowX-1] >= -1){
				cost[nowY][nowX-1] = c+1;
				if(grid[nowY][nowX-1] >= 0){
					cost[nowY][nowX-1] = 0;
					parent[grid[nowY][nowX-1]] = MP(par,c);
					que.push(MP(MP(0,grid[nowY][nowX-1]),MP(nowY,nowX-1)));
					que.push(MP(MP(-c,par),MP(nowY,nowX)));
					continue;
				}
				else{
					que.push(MP(MP(-c-1,par),MP(nowY,nowX-1)));
				}
			}
			if(nowX+1 < W && cost[nowY][nowX+1] > c+1 && grid[nowY][nowX+1] >= -1){
				cost[nowY][nowX+1] = c+1;
				if(grid[nowY][nowX+1] >= 0){
					cost[nowY][nowX+1] = 0;
					parent[grid[nowY][nowX+1]] = MP(par,c);
					que.push(MP(MP(0,grid[nowY][nowX+1]),MP(nowY,nowX+1)));

				}
				else{
					que.push(MP(MP(-c-1,par),MP(nowY,nowX+1)));
				}
			}
		}
	}

	for(int i=0; i<P; i++) culD(i);
	for(int q=0; q<Q; q++){
		int a,b;
		cin >> a >> b;
		a--; b--;
		int c = 0;
		while(a != b){
			if(depth[a] > depth[b]){
				for(int i=0; i<30; i++){
					if(dub(a,i).first == -1 || depth[dub(a,i).first] <= depth[b]){
						c = max(c, dub(a,i-1).second);
						a = dub(a,i-1).first;
						break;
					}
				}
				c = max(c, parent[a].second);
				a = parent[a].first;
			}
			else if(depth[a] < depth[b]){
				for(int i=0; i<30; i++){
					if(dub(b,i).first == -1 || depth[dub(b,i).first] <= depth[a]){
						c = max(c, dub(b,i-1).second);
						b = dub(b,i-1).first;
						break;
					}
				}
				c = max(c, parent[b].second);
				b = parent[b].first;
			}
			else{
				for(int i=0; i<30; i++){
					if(dub(a,i).first == dub(b,i).first){
						c = max(c, dub(a,i-1).second);
						c = max(c, dub(b,i-1).second);
						a = dub(a,i-1).first;
						b = dub(b,i-1).first;
						break;
					}
				}
				c = max(c, parent[a].second);
				a = parent[a].first;
				c = max(c, parent[b].second);
				b = parent[b].first;
			}
		}
		if(a == -1) cout << -1 << endl;
		else cout << c << endl;
	}

	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30