Submission #163195

#	Time	Username	Problem	Language	Result	Execution time	Memory
163195		TadijaSebez	물병 (JOI14_bottle)	C++11	100 / 100	1350 ms	99156 KiB

bottle

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mt make_tuple
const int M=2050;
const int N=200050;
const int L=19;
char base[M][M];
int dist[M][M],my[M][M];
int mv[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int par[N][L],mx[N][L],p[N];
int Find(int x){ return p[x]?p[x]=Find(p[x]):x;}
vector<int> E[N];
int dep[N];
void DFS(int u){ for(int v:E[u]) dep[v]=dep[u]+1,DFS(v);}
int LCA(int u, int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=L-1;~i;i--) if(dep[par[u][i]]>=dep[v]) u=par[u][i];
	for(int i=L-1;~i;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
	return u==v?v:par[v][0];
}
int Get(int u, int k)
{
	int ans=0;
	for(int i=0;i<L;i++) if(k>>i&1) ans=max(ans,mx[u][i]),u=par[u][i];
	return ans;
}
int main()
{
	int n,m,p,q;
	scanf("%i %i %i %i",&n,&m,&p,&q);
	for(int i=1;i<=n;i++) scanf("%s",base[i]+1);
	queue<int> qu;
	for(int i=1,x,y;i<=p;i++)
	{
		scanf("%i %i",&x,&y);
		my[x][y]=i;
		qu.push(x*M+y);
	}
	while(qu.size())
	{
		int x=qu.front()/M,y=qu.front()%M;
		qu.pop();
		for(int i=0;i<4;i++)
		{
			int nx=x+mv[i][0];
			int ny=y+mv[i][1];
			if(base[nx][ny]=='.' && !my[nx][ny])
			{
				my[nx][ny]=my[x][y];
				dist[nx][ny]=dist[x][y]+1;
				qu.push(nx*M+ny);
			}
		}
	}
	vector<tuple<int,int,int>> edges;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(base[i][j]=='.')
	{
		for(int k=0;k<2;k++)
		{
			int x=i+mv[k][0];
			int y=j+mv[k][1];
			if(base[x][y]=='.' && my[x][y]!=my[i][j])
			{
				edges.pb(mt(dist[i][j]+dist[x][y],my[i][j],my[x][y]));
			}
		}
	}
	sort(edges.begin(),edges.end());
	for(auto e:edges)
	{
		int w,u,v;tie(w,u,v)=e;
		if(Find(u)!=Find(v))
		{
			::p[u=Find(u)]=v=Find(v);
			par[u][0]=v;
			mx[u][0]=w;
		}
	}
	for(int j=1;j<L;j++) for(int i=1;i<=p;i++)
	{
		par[i][j]=par[par[i][j-1]][j-1];
		mx[i][j]=max(mx[i][j-1],mx[par[i][j-1]][j-1]);
	}
	for(int i=1;i<=p;i++) E[par[i][0]].pb(i);
	DFS(0);
	while(q--)
	{
		int x,y;
		scanf("%i %i",&x,&y);
		int z=LCA(x,y);
		if(z==0) printf("-1\n");
		else printf("%i\n",max(Get(x,dep[x]-dep[z]),Get(y,dep[y]-dep[z])));
	}
	return 0;
}

Compilation message (stderr)

bottle.cpp: In function 'int main()':
bottle.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i %i",&n,&m,&p,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:33:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%s",base[i]+1);
                        ~~~~~^~~~~~~~~~~~~~~~
bottle.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~
bottle.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30