oj.uz

Submission #199565

# Submission time Handle Problem Language Result Execution time Memory
199565 2020-02-02T04:01:33 Z arnold518 물병 (JOI14_bottle) C++14
100 / 100
 2114 ms 165612 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;
const int MAXP = 2e5;

const int dy[]={-1, 1, 0, 0};
const int dx[]={0, 0, -1, 1};

int H, W, P, QQ;
char S[MAXN+10][MAXN+10];
pii dist[MAXN+10][MAXN+10];
vector<pii> adj[MAXP+10];

struct UF
{
	int par[MAXP+10];
	UF() { for(int i=1; i<=MAXP; i++) par[i]=i; }
	int Find(int x) { return x==par[x] ? x : par[x]=Find(par[x]); }
	void Union(int x, int y) { x=Find(x); y=Find(y); par[x]=y; }
}uf;

int par[MAXP+10][30], dep[MAXP+10], val[MAXP+10][30];
bool vis[MAXP+10];

void dfs(int now, int bef, int depth)
{
	vis[now]=true;
	dep[now]=depth;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		par[nxt.first][0]=now;
		val[nxt.first][0]=nxt.second;
		dfs(nxt.first, now, depth+1);
	}
}

int query(int u, int v)
{
	int i, j, ans=0;
	if(dep[u]>dep[v]) swap(u, v);
	for(i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) ans=max(ans, val[v][i]), v=par[v][i];
	if(u==v) return ans;
	for(i=20; i>=0; i--) if(par[v][i]!=par[u][i])
	{
		ans=max(ans, val[v][i]);
		ans=max(ans, val[u][i]);
		u=par[u][i];
		v=par[v][i];
	}
	ans=max(ans, val[v][0]);
	ans=max(ans, val[u][0]);
	return ans;
}

int main()
{
	int i, j;

	scanf("%d%d%d%d", &H, &W, &P, &QQ);
	for(i=1; i<=H; i++) scanf("%s", S[i]+1);
	
	queue<pii> Q;
	for(i=1; i<=P; i++)
	{
		int y, x;
		scanf("%d%d", &y, &x);
		dist[y][x]={i, 0};
		Q.push({y, x});
	}

	int bef=-1;
	while(!Q.empty())
	{
		pii now=Q.front(); Q.pop();
		for(i=0; i<4; i++)
		{
			int ny=now.first+dy[i], nx=now.second+dx[i];
			if(!(1<=ny && ny<=H && 1<=nx && nx<=W)) continue;
			if(S[ny][nx]=='#') continue;
			if(dist[ny][nx].first==0)
			{
				dist[ny][nx]=dist[now.first][now.second];
				dist[ny][nx].second++;
				Q.push({ny, nx});
			}
		}
	}

	vector<pair<int, pii>> V;
	for(i=1; i<=H; i++) for(j=1; j<W; j++)
	{
		int c1=dist[i][j].first, c2=dist[i][j+1].first, d=dist[i][j].second+dist[i][j+1].second;
		if(c1==0 || c2==0) continue;
		V.push_back({d, {c1, c2}});
	}

	for(i=1; i<H; i++) for(j=1; j<=W; j++)
	{
		int c1=dist[i][j].first, c2=dist[i+1][j].first, d=dist[i][j].second+dist[i+1][j].second;
		if(c1==0 || c2==0) continue;
		V.push_back({d, {c1, c2}});
	}
	sort(V.begin(), V.end());
	for(auto it : V)
	{
		if(uf.Find(it.second.first)!=uf.Find(it.second.second))
		{
			uf.Union(it.second.first, it.second.second);
			adj[it.second.first].push_back({it.second.second, it.first});
			adj[it.second.second].push_back({it.second.first, it.first});
		}
	}

	for(i=1; i<=P; i++)
	{
		if(vis[i]) continue;
		dfs(i, i, 1);
	}
	for(i=1; i<=20; i++) for(j=1; j<=P; j++) val[j][i]=max(val[j][i-1], val[par[j][i-1]][i-1]), par[j][i]=par[par[j][i-1]][i-1];
	while(QQ--)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		if(uf.Find(u)!=uf.Find(v)) printf("-1\n");
		else printf("%d\n", query(u, v));
	}
}

Compilation message

bottle.cpp: In function 'int query(int, int)':
bottle.cpp:45:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, ans=0;
         ^
bottle.cpp: In function 'int main()':
bottle.cpp:77:6: warning: unused variable 'bef' [-Wunused-variable]
  int bef=-1;
      ^~~
bottle.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &H, &W, &P, &QQ);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:66:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=H; i++) scanf("%s", S[i]+1);
                      ~~~~~^~~~~~~~~~~~~~
bottle.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &y, &x);
   ~~~~~^~~~~~~~~~~~~~~~
bottle.cpp:129:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6592 KB Output is correct
2 Correct 14 ms 7620 KB Output is correct
3 Correct 17 ms 8316 KB Output is correct
4 Correct 123 ms 9948 KB Output is correct
5 Correct 113 ms 9976 KB Output is correct
6 Correct 122 ms 9724 KB Output is correct
7 Correct 109 ms 9852 KB Output is correct
8 Correct 132 ms 10360 KB Output is correct
9 Correct 107 ms 9976 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 22656 KB Output is correct
2 Correct 101 ms 15776 KB Output is correct
3 Correct 798 ms 94700 KB Output is correct
4 Correct 1091 ms 95152 KB Output is correct
5 Correct 1309 ms 144732 KB Output is correct
6 Correct 748 ms 94696 KB Output is correct
7 Correct 1057 ms 95280 KB Output is correct
8 Correct 1262 ms 144536 KB Output is correct
9 Correct 1674 ms 145152 KB Output is correct
10 Correct 919 ms 94828 KB Output is correct
11 Correct 983 ms 95104 KB Output is correct
12 Correct 433 ms 84332 KB Output is correct
13 Correct 544 ms 84188 KB Output is correct
14 Correct 407 ms 84332 KB Output is correct
15 Correct 573 ms 84320 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 22656 KB Output is correct
2 Correct 88 ms 16148 KB Output is correct
3 Correct 612 ms 94788 KB Output is correct
4 Correct 1037 ms 95148 KB Output is correct
5 Correct 1265 ms 144812 KB Output is correct
6 Correct 1693 ms 145264 KB Output is correct
7 Correct 927 ms 94828 KB Output is correct
8 Correct 1002 ms 95280 KB Output is correct
9 Correct 453 ms 84460 KB Output is correct
10 Correct 561 ms 84188 KB Output is correct
11 Correct 464 ms 58972 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 915 ms 90988 KB Output is correct
2 Correct 1498 ms 137868 KB Output is correct
3 Correct 954 ms 94832 KB Output is correct
4 Correct 1884 ms 151232 KB Output is correct
5 Correct 2114 ms 165612 KB Output is correct
6 Correct 1188 ms 99076 KB Output is correct
7 Correct 936 ms 94700 KB Output is correct
8 Correct 416 ms 84184 KB Output is correct
9 Correct 1893 ms 158696 KB Output is correct
10 Correct 1462 ms 126564 KB Output is correct
11 Correct 1978 ms 163088 KB Output is correct
12 Correct 1816 ms 148904 KB Output is correct