oj.uz

Submission #906989

# Submission time Handle Problem Language Result Execution time Memory
906989 2024-01-15T05:33:30 Z pan 물병 (JOI14_bottle) C++17
100 / 100
 2192 ms 221452 KB 
#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;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13208 KB Output is correct
2 Correct 9 ms 17664 KB Output is correct
3 Correct 10 ms 17500 KB Output is correct
4 Correct 327 ms 19532 KB Output is correct
5 Correct 321 ms 19540 KB Output is correct
6 Correct 312 ms 19540 KB Output is correct
7 Correct 310 ms 19364 KB Output is correct
8 Correct 342 ms 19896 KB Output is correct
9 Correct 373 ms 19688 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 78020 KB Output is correct
2 Correct 57 ms 22164 KB Output is correct
3 Correct 623 ms 90820 KB Output is correct
4 Correct 822 ms 93936 KB Output is correct
5 Correct 872 ms 98416 KB Output is correct
6 Correct 576 ms 90724 KB Output is correct
7 Correct 799 ms 94124 KB Output is correct
8 Correct 903 ms 96668 KB Output is correct
9 Correct 1228 ms 102836 KB Output is correct
10 Correct 618 ms 90988 KB Output is correct
11 Correct 671 ms 93156 KB Output is correct
12 Correct 197 ms 93308 KB Output is correct
13 Correct 301 ms 90636 KB Output is correct
14 Correct 166 ms 93392 KB Output is correct
15 Correct 207 ms 90596 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 77956 KB Output is correct
2 Correct 43 ms 21284 KB Output is correct
3 Correct 320 ms 89828 KB Output is correct
4 Correct 762 ms 94304 KB Output is correct
5 Correct 963 ms 96252 KB Output is correct
6 Correct 1157 ms 103524 KB Output is correct
7 Correct 483 ms 90936 KB Output is correct
8 Correct 750 ms 93784 KB Output is correct
9 Correct 248 ms 93040 KB Output is correct
10 Correct 288 ms 90656 KB Output is correct
11 Correct 270 ms 90328 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 967 ms 94564 KB Output is correct
2 Correct 1553 ms 192336 KB Output is correct
3 Correct 699 ms 90856 KB Output is correct
4 Correct 2052 ms 200584 KB Output is correct
5 Correct 2192 ms 217748 KB Output is correct
6 Correct 1273 ms 105460 KB Output is correct
7 Correct 682 ms 90888 KB Output is correct
8 Correct 164 ms 90528 KB Output is correct
9 Correct 1958 ms 221452 KB Output is correct
10 Correct 1870 ms 199888 KB Output is correct
11 Correct 2051 ms 219652 KB Output is correct
12 Correct 1985 ms 208752 KB Output is correct