oj.uz

Submission #156099

# Submission time Handle Problem Language Result Execution time Memory
156099 2019-10-03T09:46:08 Z puppies_and_rainbows 물병 (JOI14_bottle) C++14
70 / 100
 5000 ms 242996 KB 
#include <bits/stdc++.h>
#define union khoaphamdangyeuhihixd
using namespace std;

int h1, w, p, q;

int last[2005][2005], dist[2005][2005];
queue<pair<int, int> > b;
string s[2005];
vector<pair<int, int> > adj[200005];
int dx[]={0, 1, 0, -1};
int dy[]={-1, 0, 1, 0};
vector<pair<int, pair<int, int> > > edges;
int f[200005], h[200005];
pair<int, int>  anc[200005][20];

int find(int i)
{
	return f[i]==i ? f[i] : find(f[i]); 
}

void union(int i, int j)
{
	f[find(i)]=find(j);
}

bool check(int a, int b)
{
	if(a>0 && b>0 && a<=h1 && b<=w && s[a][b]!='#' && last[a][b]==0)
	{
		return true;
	}
	return false;
}

void bfs()
{
	while(b.size())
	{
		pair<int, int> fr=b.front();
		b.pop();
		for(int i=0; i<4; i++)
		{
			int ax=fr.first+dx[i], ay=fr.second+dy[i], ck=check(ax, ay);
			if(ck)
			{
				last[ax][ay]=last[fr.first][fr.second];
				dist[ax][ay]=dist[fr.first][fr.second]+1;
				b.push({ax, ay});
			}
			else if(last[ax][ay]!=0)
			{
			 	edges.push_back({dist[ax][ay]+dist[fr.first][fr.second],{last[ax][ay], last[fr.first][fr.second]}});
			}
		}	
	}
}

void kruskal()
{
	sort(edges.begin(), edges.end());
	for(auto i:edges)
	{
		if(find(i.second.second)!=find(i.second.first))
		{
			union(i.second.first, i.second.second);
			adj[i.second.first].push_back({i.second.second, i.first});
			adj[i.second.second].push_back({i.second.first, i.first});
		}
	}
}

bool visited[200005];

void dfs(int node, int fa)
{
	visited[node]=1;
	h[node]=h[fa]+1;
	anc[node][0].first=fa;
	for(int i=1; i<=19; i++)
	{
		anc[node][i].first=anc[anc[node][i-1].first][i-1].first;
		anc[node][i].second=max(anc[node][i-1].second, anc[anc[node][i-1].first][i-1].second);
	}
	for(auto i:adj[node])
	{
		if(i.first==fa)
		{
		 	continue;
		}
		anc[i.first][0].second=i.second;
		dfs(i.first, node);
	}
}

int lca(int u, int v)
{
	// cout<<u<<" "<<v<<endl;
	int lel=0;
	if(h[u]<h[v])
	{
		swap(u, v);
	}
	for(int i=18; i>=0; i--)
	{
		if(h[anc[u][i].first]<h[v]) continue;
		lel=max(lel, anc[u][i].second);
		u=anc[u][i].first;
	}
	// cout<<u<<endl;
	if(u==v) return lel;
	for(int i=18; i>=0; i--)
	{
		if(anc[u][i].first==anc[v][i].first) continue;
		lel=max(lel, max(anc[u][i].second, anc[v][i].second));
		u=anc[u][i].first;
		v=anc[v][i].first;
	}
	return max(lel, max(anc[u][0].second, anc[v][0].second));
}

signed main()
{
	cin>>h1>>w>>p>>q;
	for(int i=1; i<=p; i++)
	{
		f[i]=i;
	}
	for(int i=1; i<=h1; i++)
	{
		cin>>s[i];
		s[i]='!'+s[i]+'!';
	}
	for(int i=1; i<=p; i++)
	{
		int u, v;
		cin>>u>>v;
		b.push({u, v});
		last[u][v]=i;
	}
	bfs();
	kruskal();
	for(int i=1; i<=p; i++)
	{
		if(!visited[i])
		{
			dfs(i, i);
		}
	}
	// for(int i=1; i<=h1; i++)
	// {
	// 	for(int j=1; j<=w; j++)
	// 	{
	// 		cout<<last[i][j]<<" ";
	// 	}
	// 	cout<<endl;
	// }
	for(int i=1; i<=q; i++)
	{
		int u, v;
		cin>>u>>v;
		// cout<<find(u)<<" "<<find(v)<<endl;
		if(find(u)==find(v)) cout<<lca(u, v)<<endl;
		else cout<<-1<<endl;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6204 KB Output is correct
2 Correct 20 ms 7360 KB Output is correct
3 Correct 25 ms 7928 KB Output is correct
4 Correct 731 ms 8580 KB Output is correct
5 Correct 740 ms 8568 KB Output is correct
6 Correct 733 ms 8176 KB Output is correct
7 Correct 724 ms 8328 KB Output is correct
8 Correct 746 ms 8948 KB Output is correct
9 Correct 721 ms 8664 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 26544 KB Output is correct
2 Correct 170 ms 16100 KB Output is correct
3 Correct 962 ms 93956 KB Output is correct
4 Correct 1941 ms 143428 KB Output is correct
5 Correct 2401 ms 144000 KB Output is correct
6 Correct 989 ms 93888 KB Output is correct
7 Correct 2176 ms 143740 KB Output is correct
8 Correct 2338 ms 144020 KB Output is correct
9 Correct 3601 ms 242932 KB Output is correct
10 Correct 1109 ms 143224 KB Output is correct
11 Correct 1359 ms 143548 KB Output is correct
12 Correct 702 ms 83928 KB Output is correct
13 Correct 786 ms 86360 KB Output is correct
14 Correct 722 ms 83824 KB Output is correct
15 Correct 779 ms 84992 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 26596 KB Output is correct
2 Correct 118 ms 15304 KB Output is correct
3 Correct 813 ms 93756 KB Output is correct
4 Correct 1804 ms 143624 KB Output is correct
5 Correct 2438 ms 144004 KB Output is correct
6 Correct 4075 ms 242996 KB Output is correct
7 Correct 1373 ms 143188 KB Output is correct
8 Correct 1897 ms 143688 KB Output is correct
9 Correct 763 ms 83928 KB Output is correct
10 Correct 816 ms 85564 KB Output is correct
11 Correct 785 ms 61612 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2141 ms 94068 KB Output is correct
2 Correct 4357 ms 126868 KB Output is correct
3 Correct 1226 ms 143316 KB Output is correct
4 Execution timed out 5097 ms 148604 KB Time limit exceeded
5 Halted 0 ms 0 KB -