oj.uz

Submission #105701

# Submission time Handle Problem Language Result Execution time Memory
105701 2019-04-14T04:15:34 Z Pro_ktmr 물병 (JOI14_bottle) C++14
100 / 100
 2997 ms 100464 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1024 KB Output is correct
2 Correct 12 ms 2176 KB Output is correct
3 Correct 15 ms 2432 KB Output is correct
4 Correct 400 ms 4492 KB Output is correct
5 Correct 379 ms 4344 KB Output is correct
6 Correct 391 ms 4460 KB Output is correct
7 Correct 496 ms 4344 KB Output is correct
8 Correct 373 ms 4520 KB Output is correct
9 Correct 411 ms 4576 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 18400 KB Output is correct
2 Correct 96 ms 5420 KB Output is correct
3 Correct 540 ms 36508 KB Output is correct
4 Correct 830 ms 36828 KB Output is correct
5 Correct 900 ms 37352 KB Output is correct
6 Correct 535 ms 36500 KB Output is correct
7 Correct 865 ms 36960 KB Output is correct
8 Correct 939 ms 37100 KB Output is correct
9 Correct 1099 ms 37056 KB Output is correct
10 Correct 863 ms 36164 KB Output is correct
11 Correct 886 ms 36232 KB Output is correct
12 Correct 287 ms 36620 KB Output is correct
13 Correct 308 ms 37212 KB Output is correct
14 Correct 281 ms 37132 KB Output is correct
15 Correct 269 ms 36976 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 18508 KB Output is correct
2 Correct 90 ms 4300 KB Output is correct
3 Correct 578 ms 35940 KB Output is correct
4 Correct 854 ms 37312 KB Output is correct
5 Correct 1042 ms 37600 KB Output is correct
6 Correct 1091 ms 37856 KB Output is correct
7 Correct 770 ms 36076 KB Output is correct
8 Correct 820 ms 37620 KB Output is correct
9 Correct 252 ms 37516 KB Output is correct
10 Correct 270 ms 37700 KB Output is correct
11 Correct 189 ms 37280 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1141 ms 41256 KB Output is correct
2 Correct 2338 ms 97424 KB Output is correct
3 Correct 884 ms 36044 KB Output is correct
4 Correct 2762 ms 98436 KB Output is correct
5 Correct 2997 ms 99872 KB Output is correct
6 Correct 1512 ms 45000 KB Output is correct
7 Correct 807 ms 36040 KB Output is correct
8 Correct 237 ms 35876 KB Output is correct
9 Correct 2418 ms 99640 KB Output is correct
10 Correct 2506 ms 100464 KB Output is correct
11 Correct 2969 ms 100136 KB Output is correct
12 Correct 2671 ms 100432 KB Output is correct