제출 #906989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
906989		pan	물병 (JOI14_bottle)	C++17	100 / 100	2192 ms	221452 KiB

bottle

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
ll h,w,p, question;
vector<string> m;
ll const MAXN = 200005;
ll const s = 2005;
ll dist[s][s];
bool visited[s][s];
ll par[s][s];
ll twok[MAXN][25];
ll max2k[MAXN][25];
ll depth[MAXN];
ll dx[4] = {0, 1, -1, 0};
ll dy[4] = {1, 0, 0, -1};
vector<pi> adj[MAXN];
vector<pii> edges;
bool compare(pii a, pii b)
{
	return a.f<b.f;
}
vector<ll> link, siz;

ll find(ll a) {
    ll b = a;
    if (link[a] != a) {
        b = find(link[a]);
    }
    link[a] = b;
    return b;
}
bool same(ll a, ll b)
{
	return find(a)==find(b);
}

void unite(ll a, ll b) {
    ll p1 = find(a);
    ll p2 = find(b);
    if (p1 != p2) {
        if (siz[p1] > siz[p2]) {
            swap(p1, p2);
        }
        link[p1] = p2;
        siz[p2] += siz[p1];
    }
}
void dfs(ll p, ll node)
{
	
	for (pi u: adj[node])
	{
		if (p==u.f) continue;
		twok[u.f][0] = node;
		max2k[u.f][0] = u.s;
		depth[u.f] = depth[node]+1;
		dfs(node, u.f);
	}
	
}

void init()
{
	for (ll k=1; k<20; k++)
	{
		for (ll x=0; x<p; ++x)
		{
			if (twok[x][k-1]==-1) continue;
			twok[x][k] = twok[twok[x][k-1]][k-1];
			max2k[x][k] = max(max2k[x][k-1], max2k[twok[x][k-1]][k-1]);
			//show3(x, k, max2k[x][k]);
		}
	}
}


ll lca(ll a, ll b)
{
	ll ans = 0;
	if (depth[a]<depth[b]) swap(a,b);
	ll up = depth[a]-depth[b];
	for (ll i=0; i<20; ++i)
	{
		if (up& (1<<i)) 
		{
			ans = max(ans, max2k[a][i]);
			a=twok[a][i];
		}
	}
	if (a==b) return ans;
	for (ll k=19; k>=0; k--)
	{
		if (twok[a][k]!=twok[b][k])
		{
			ans = max(ans, max2k[a][k]);
			ans = max(ans, max2k[b][k]);
			a=twok[a][k]; b = twok[b][k];
		}
	}
	ans = max(ans, max2k[b][0]);
	ans = max(ans, max2k[a][0]);
	return ans;
	
}

int main()
{
	cin >> h >> w >> p >> question;
	m.resize(h);
	for (ll i=0; i<h; ++i) cin >> m[i];
	queue<pii> q;
	for (ll i=0; i<h; ++i) {for (ll j=0; j<w; ++j){ dist[i][j]=LLONG_MAX;par[i][j] = -1;}}
	link.resize(p);
	siz.assign(p, 1);
	for (ll i=0; i<p; ++i)
	{
		ll x,y;
		cin >> x >> y;
		--x, --y;
		dist[x][y] = 0;
		link[i]=i;
		par[x][y] = i;
		q.push(mp(i, mp(x,y)));
	}
	// use bfs to find shortest edges between building
	while (q.size())
	{
		ll b = q.front().f, x = q.front().s.f, y = q.front().s.s;
		q.pop();
		if (visited[x][y]) continue;
		visited[x][y] = true;
		for (ll k=0; k<4; ++k)
		{
			ll newx = x+dx[k], newy = y+dy[k];
			if (newx<0 || newx>=h || newy<0 || newy>=w || m[newx][newy]=='#') continue;
			if (dist[newx][newy]>dist[x][y]+1)
			{
				dist[newx][newy] = dist[x][y]+1;
				par[newx][newy] = b;
				q.push(mp(b, mp(newx, newy)));
			}
	
		}
		
	}
	
	for (ll x=0; x<h; ++x)
	{
		for (ll y=0; y<w; ++y)
		{
			if (m[x][y]=='#') continue;
			for (ll k=0; k<=1; ++k)
			{
				ll newx = x+dx[k], newy = y+dy[k];
				if (newx<0 || newx>=h || newy<0 || newy>=w || m[newx][newy]=='#') continue;
				if (par[x][y]!=par[newx][newy] && par[x][y]!=-1 && par[newx][newy]!=-1)
				{
					edges.pb(mp(dist[x][y]+dist[newx][newy]+1, mp(par[x][y], par[newx][newy])));
				}
			}
		}
	}
	sort(edges.begin(), edges.end(), compare);
	// Krushkal's MST algorithm
	for (ll i=0; i<edges.size(); ++i)
	{
		
		ll from = edges[i].s.f, to = edges[i].s.s, c = edges[i].f;
		if (same(from ,to)) continue;
		unite(from, to);
		adj[from].pb(mp(to, c));
		adj[to].pb(mp(from, c));
		//show3(from, to, c);
	}
	// 2k decomp
	for (ll k=0; k<20; k++) {for (ll x=0; x<p; ++x) twok[x][k] = -1; }
	for (ll i=0; i<p; ++i) {if (depth[i]==0) {dfs(-1,i);}}
	init();
	//for (ll k=0; k<2; k++) {for (ll x=0; x<p; ++x) {show3(x,k,twok[x][k]);} }
	while (question--)
	{
		ll x,y;
		cin >> x >> y;
		--x, --y;
		if (!same(x, y)) cout << -1 << endl;
		else cout << lca(x, y)-1 << endl;
	}
	
	
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bottle.cpp: In function 'int main()':
bottle.cpp:180:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |  for (ll i=0; i<edges.size(); ++i)
      |               ~^~~~~~~~~~~~~

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