oj.uz

답안 #156106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
156106 2019-10-03T11:43:55 Z shuvi_dola 물병 (JOI14_bottle) C++14
10 / 100
 507 ms 44708 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[N];
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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 5880 KB Output is correct
2 Correct 10 ms 7416 KB Output is correct
3 Correct 12 ms 7672 KB Output is correct
4 Correct 93 ms 8312 KB Output is correct
5 Correct 96 ms 8384 KB Output is correct
6 Correct 92 ms 8312 KB Output is correct
7 Correct 87 ms 8312 KB Output is correct
8 Correct 97 ms 8644 KB Output is correct
9 Correct 87 ms 8424 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 27312 KB Output is correct
2 Incorrect 50 ms 10764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 27240 KB Output is correct
2 Correct 44 ms 9492 KB Output is correct
3 Correct 286 ms 40888 KB Output is correct
4 Incorrect 494 ms 44708 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 507 ms 44256 KB Output isn't correct
2 Halted 0 ms 0 KB -