oj.uz

Submission #156107

# Submission time Handle Problem Language Result Execution time Memory
156107 2019-10-03T11:44:55 Z shuvi_dola 물병 (JOI14_bottle) C++14
100 / 100
 1769 ms 126136 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const int P = 2e5 + 5;
const int Tx[] = {-1, 0, 1, 0};
const int Ty[] = {0, 1, 0, -1};
typedef pair <int,int> pi;
char a[N][N];
int dist[N][N], id[N][N];
queue <pi> q;
vector <pair <int, pi> > edge;
int dep[P], up[P][25], anc[P][25];
int link[P], size[P];
vector <pi> g[P];
int H, W, p, que;
bool vis[P];

void dfs(int u, int p)
{
	vis[u] = 1;
	for(int i = 1; i <= 20; i++)
	{
		anc[u][i] = anc[anc[u][i - 1]][i - 1];
		up[u][i] = max(up[u][i - 1], up[anc[u][i - 1]][i - 1]);
	}
	for(auto x : g[u])
	{
		int v = x.first, w = x.second;
		if(v == p)
			continue;
		dep[v] = dep[u] + 1, 
		anc[v][0] = u, up[v][0] = w;
		dfs(v, u);
	}
}

void init()
{ for(int i=1;i<=p;i++) link[i] = i; for(int i=1;i<=p;i++) size[i] = 1; }
int find(int x)
{ while(x != link[x]) x = link[x]; return x; }
bool same(int a,int b)
{ return find(a) == find(b); }
void unite(int a,int b)
{ a = find(a); b = find(b); if(size[a] < size[b]) swap(a,b); size[a] += size[b]; link[b] = a; }

bool ck(int x, int y)
{ return (x >= 1 && y >= 1 && x <= H && y <= W && a[x][y] == '.'); }

int max_path(int u, int v)
{
    if (!same(u, v)) return -1;
    int ans = 0;
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20; i >= 0; --i) if (dep[u] - (1 << i) >= dep[v]) ans = max(ans, up[u][i]), u = anc[u][i];
    if (u == v) return ans;
    for (int i = 20; i >= 0; --i) if (anc[u][i] != anc[v][i]) ans = max(ans, max(up[u][i], up[v][i])), u = anc[u][i], v = anc[v][i];
    return max(ans, max(up[u][0], up[v][0]));
}

void bfs()
{
	while(q.size() > 0)
	{
		int x = q.front().first,
			y = q.front().second;
		q.pop();
		for(int i = 0; i < 4; i++)
		{
			int nx = x + Tx[i], ny = y + Ty[i];
			if(ck(nx, ny) && dist[nx][ny] == -1)
			{
				dist[nx][ny] = dist[x][y] + 1, 
				id[nx][ny] = id[x][y];
				q.push({nx, ny});
			}
			if(ck(nx, ny) && dist[nx][ny] != -1)
			{
				int a = id[nx][ny], b = id[x][y];
				if(a != b)
					edge.push_back({dist[nx][ny] + dist[x][y], {a, b}});
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> H >> W >> p >> que;
	init();
	for(int i = 1; i <= H; i++)
	{
		for(int j = 1; j <= W; j++)
		{
			dist[i][j] = -1;
			id[i][j] = 0;
			cin >> a[i][j];
		}
	}
	for(int i = 1; i <= p; i++)
	{
		int x, y; cin >> x >> y;
		dist[x][y] = 0;
		id[x][y] = i;
		q.push({x, y});
	}
	bfs();
	sort(edge.begin(), edge.end());
	for(auto e : edge)
	{
		int x = e.second.first, y = e.second.second;
		if(!same(x, y))
		{
			g[x].push_back({y, e.first});
			g[y].push_back({x, e.first});
			unite(x, y);
		}
	}
	for(int i = 1; i <= p; i++)
	{
		if(!vis[i])
			dfs(i, i);
	}	
	while(que--)
	{
		int s, t;
		cin >> s >> t;
		cout << max_path(s, t) << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5884 KB Output is correct
2 Correct 12 ms 7416 KB Output is correct
3 Correct 14 ms 7544 KB Output is correct
4 Correct 94 ms 8152 KB Output is correct
5 Correct 95 ms 8296 KB Output is correct
6 Correct 92 ms 8196 KB Output is correct
7 Correct 91 ms 8056 KB Output is correct
8 Correct 100 ms 8504 KB Output is correct
9 Correct 86 ms 8440 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 27396 KB Output is correct
2 Correct 50 ms 10796 KB Output is correct
3 Correct 335 ms 42412 KB Output is correct
4 Correct 504 ms 44720 KB Output is correct
5 Correct 558 ms 47772 KB Output is correct
6 Correct 367 ms 42424 KB Output is correct
7 Correct 520 ms 44836 KB Output is correct
8 Correct 699 ms 47988 KB Output is correct
9 Correct 713 ms 54436 KB Output is correct
10 Correct 412 ms 42416 KB Output is correct
11 Correct 432 ms 44176 KB Output is correct
12 Correct 224 ms 44612 KB Output is correct
13 Correct 249 ms 42404 KB Output is correct
14 Correct 212 ms 44712 KB Output is correct
15 Correct 246 ms 42488 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 27268 KB Output is correct
2 Correct 40 ms 9368 KB Output is correct
3 Correct 290 ms 40712 KB Output is correct
4 Correct 492 ms 44740 KB Output is correct
5 Correct 590 ms 48024 KB Output is correct
6 Correct 813 ms 54400 KB Output is correct
7 Correct 357 ms 42492 KB Output is correct
8 Correct 456 ms 44876 KB Output is correct
9 Correct 227 ms 44704 KB Output is correct
10 Correct 258 ms 42712 KB Output is correct
11 Correct 249 ms 42156 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 44304 KB Output is correct
2 Correct 1071 ms 99052 KB Output is correct
3 Correct 362 ms 42416 KB Output is correct
4 Correct 1377 ms 107172 KB Output is correct
5 Correct 1769 ms 117580 KB Output is correct
6 Correct 746 ms 51660 KB Output is correct
7 Correct 363 ms 42524 KB Output is correct
8 Correct 174 ms 41640 KB Output is correct
9 Correct 1575 ms 126136 KB Output is correct
10 Correct 1093 ms 103576 KB Output is correct
11 Correct 1535 ms 121196 KB Output is correct
12 Correct 1241 ms 112140 KB Output is correct