oj.uz

Submission #163195

# Submission time Handle Problem Language Result Execution time Memory
163195 2019-11-11T18:01:02 Z TadijaSebez 물병 (JOI14_bottle) C++11
100 / 100
 1350 ms 99156 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5752 KB Output is correct
2 Correct 12 ms 7288 KB Output is correct
3 Correct 12 ms 7416 KB Output is correct
4 Correct 136 ms 9464 KB Output is correct
5 Correct 136 ms 9528 KB Output is correct
6 Correct 133 ms 9200 KB Output is correct
7 Correct 130 ms 9396 KB Output is correct
8 Correct 139 ms 9964 KB Output is correct
9 Correct 137 ms 9744 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 27504 KB Output is correct
2 Correct 42 ms 10452 KB Output is correct
3 Correct 319 ms 46420 KB Output is correct
4 Correct 469 ms 47528 KB Output is correct
5 Correct 462 ms 48880 KB Output is correct
6 Correct 327 ms 46372 KB Output is correct
7 Correct 422 ms 47656 KB Output is correct
8 Correct 486 ms 48756 KB Output is correct
9 Correct 514 ms 52148 KB Output is correct
10 Correct 328 ms 46176 KB Output is correct
11 Correct 399 ms 47024 KB Output is correct
12 Correct 147 ms 40440 KB Output is correct
13 Correct 190 ms 39308 KB Output is correct
14 Correct 138 ms 40360 KB Output is correct
15 Correct 185 ms 39264 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 27332 KB Output is correct
2 Correct 36 ms 9552 KB Output is correct
3 Correct 280 ms 45304 KB Output is correct
4 Correct 459 ms 47568 KB Output is correct
5 Correct 471 ms 48880 KB Output is correct
6 Correct 540 ms 52172 KB Output is correct
7 Correct 335 ms 46168 KB Output is correct
8 Correct 443 ms 47676 KB Output is correct
9 Correct 156 ms 40488 KB Output is correct
10 Correct 193 ms 39548 KB Output is correct
11 Correct 187 ms 38428 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 50020 KB Output is correct
2 Correct 1012 ms 89320 KB Output is correct
3 Correct 320 ms 46116 KB Output is correct
4 Correct 1209 ms 93248 KB Output is correct
5 Correct 1350 ms 98388 KB Output is correct
6 Correct 696 ms 54436 KB Output is correct
7 Correct 324 ms 46116 KB Output is correct
8 Correct 120 ms 38664 KB Output is correct
9 Correct 1179 ms 99156 KB Output is correct
10 Correct 816 ms 79460 KB Output is correct
11 Correct 1169 ms 93700 KB Output is correct
12 Correct 886 ms 86572 KB Output is correct