Submission #199565

#	Time	Username	Problem	Language	Result	Execution time	Memory
199565		arnold518	물병 (JOI14_bottle)	C++14	100 / 100	2114 ms	165612 KiB

bottle

#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 (stderr)

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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30