oj.uz

Submission #594891

# Submission time Handle Problem Language Result Execution time Memory
594891 2022-07-13T06:21:40 Z 장태환(#8438) 물병 (JOI14_bottle) C++14
100 / 100
 1865 ms 123952 KB 
#include <bits/stdc++.h>
using namespace std;
int N, M,P,Q;
string a[2010];
pair<int, int>tt[2010][2010];
vector<pair<int, pair<int, int>>>link;
vector<pair<int, int>>tree[200100];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<pair<int, int>>x;
int uf[200100];
pair<int,int> lca[200100][20];
int d[200100];
int f(int n)
{
	return uf[n] == n ? n : uf[n] = f(uf[n]);
}
void dfs(int n, int p=0)
{
	int i;
	for (i = 0; i < 19; i++)
	{
		lca[n][i + 1].first = lca[lca[n][i].first][i].first;
		lca[n][i + 1].second = max(lca[lca[n][i].first][i].second, lca[n][i].second);
	}
	for (i = 0; i < tree[n].size(); i++)
	{
		if (tree[n][i].first == p)
			continue;
		d[tree[n][i].first] = d[n] + 1;
		lca[tree[n][i].first][0] = { n,tree[n][i].second };
		dfs(tree[n][i].first, n);
	}
}
int lc(int a, int b)
{
	if (d[a] < d[b])
		swap(a, b);
	int di = d[a] - d[b];
	int i;
	int ans = 0;
	for (i = 19; i >= 0; i--)
	{
		if ((di >> i) & 1)
		{
			ans = max(ans, lca[a][i].second);
			a = lca[a][i].first;
		}
	}
	if (a == b)
		return ans;
	for (i = 19; i >= 0; i--)
	{
		if (lca[a][i].first!=lca[b][i].first)
		{
			ans = max(ans, lca[a][i].second);
			ans = max(ans, lca[b][i].second);
			a = lca[a][i].first;
			b = lca[b][i].first;
		}
	}
	return max({ ans,lca[a][0].second,lca[b][0].second });
}
int main()
{
	cin >> N >> M >> P >> Q;
	int i,j;
	for (i = 0; i < N; i++)
	{
		cin >> a[i];
	}
	queue<pair<pair<int,int>, int>>bfs;
	memset(tt, 1, sizeof(tt));
	for (i = 0; i < P; i++)
	{
		int a, b;
		cin >> a >> b;
		x.push_back({ a-1,b-1 });
		bfs.push({ {a - 1,b - 1},i+1 });
		tt[a - 1][b - 1] = { 0,i + 1 };
		uf[i + 1] = i + 1;
	}
	while (bfs.size())
	{
		auto t = bfs.front();
		bfs.pop();
		for (i = 0; i < 4; i++)
		{
			int nx = t.first.first + dx[i];
			int ny = t.first.second + dy[i];
			if (nx < 0 || ny < 0 || nx >= N || ny >= M||a[nx][ny]=='#')
			{
				continue;
			}
			if (tt[nx][ny].first > tt[t.first.first][t.first.second].first+1)
			{
				tt[nx][ny] = { tt[t.first.first][t.first.second].first + 1,t.second };
				bfs.push({ {nx,ny},t.second });
			}
			else if (tt[nx][ny].second != t.second)
			{
				link.push_back({  tt[nx][ny].first + tt[t.first.first][t.first.second].first,{t.second,tt[nx][ny].second} });
			}
		}
	}
	sort(link.begin(), link.end());
	for (i = 0; i < link.size(); i++)
	{
		if (f(link[i].second.first) != f(link[i].second.second))
		{
			uf[f(link[i].second.first)] = f(link[i].second.second);
			tree[link[i].second.first].push_back({ link[i].second.second,link[i].first });
			tree[link[i].second.second].push_back({ link[i].second.first,link[i].first });
		}
	}
	for (i = 1; i <= P; i++)
	{
		if (!d[i])
		{
			dfs(i);
		}
	}
	while (Q--)
	{
		int a, b;
		cin >> a >> b;
		if (f(a) != f(b))
			cout << -1 << '\n';
		else
			cout << lc(a, b) << '\n';
	}
}

Compilation message

bottle.cpp: In function 'void dfs(int, int)':
bottle.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (i = 0; i < tree[n].size(); i++)
      |              ~~^~~~~~~~~~~~~~~~
bottle.cpp: In function 'int main()':
bottle.cpp:107:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for (i = 0; i < link.size(); i++)
      |              ~~^~~~~~~~~~~~~
bottle.cpp:67:8: warning: unused variable 'j' [-Wunused-variable]
   67 |  int i,j;
      |        ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 36820 KB Output is correct
2 Correct 21 ms 36920 KB Output is correct
3 Correct 20 ms 36808 KB Output is correct
4 Correct 355 ms 37392 KB Output is correct
5 Correct 358 ms 37452 KB Output is correct
6 Correct 349 ms 37424 KB Output is correct
7 Correct 338 ms 37612 KB Output is correct
8 Correct 343 ms 37740 KB Output is correct
9 Correct 338 ms 37636 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 37584 KB Output is correct
2 Correct 62 ms 39480 KB Output is correct
3 Correct 317 ms 46072 KB Output is correct
4 Correct 413 ms 49036 KB Output is correct
5 Correct 445 ms 52200 KB Output is correct
6 Correct 328 ms 46372 KB Output is correct
7 Correct 407 ms 49120 KB Output is correct
8 Correct 465 ms 52288 KB Output is correct
9 Correct 552 ms 58912 KB Output is correct
10 Correct 338 ms 46612 KB Output is correct
11 Correct 411 ms 48304 KB Output is correct
12 Correct 201 ms 48520 KB Output is correct
13 Correct 198 ms 46472 KB Output is correct
14 Correct 177 ms 48616 KB Output is correct
15 Correct 214 ms 46428 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 37620 KB Output is correct
2 Correct 44 ms 38228 KB Output is correct
3 Correct 262 ms 44620 KB Output is correct
4 Correct 433 ms 48768 KB Output is correct
5 Correct 478 ms 52232 KB Output is correct
6 Correct 583 ms 59000 KB Output is correct
7 Correct 388 ms 46404 KB Output is correct
8 Correct 500 ms 48928 KB Output is correct
9 Correct 250 ms 48568 KB Output is correct
10 Correct 262 ms 46544 KB Output is correct
11 Correct 242 ms 46200 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 845 ms 48000 KB Output is correct
2 Correct 1216 ms 96112 KB Output is correct
3 Correct 431 ms 46464 KB Output is correct
4 Correct 1606 ms 104088 KB Output is correct
5 Correct 1702 ms 115916 KB Output is correct
6 Correct 999 ms 55432 KB Output is correct
7 Correct 397 ms 46476 KB Output is correct
8 Correct 176 ms 45604 KB Output is correct
9 Correct 1746 ms 123952 KB Output is correct
10 Correct 1441 ms 106724 KB Output is correct
11 Correct 1865 ms 122964 KB Output is correct
12 Correct 1572 ms 114668 KB Output is correct