oj.uz

Submission #129685

# Submission time Handle Problem Language Result Execution time Memory
129685 2019-07-13T04:33:29 Z 박상수(#3145) 물병 (JOI14_bottle) C++14
100 / 100
 1518 ms 149832 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int H, W, P, Q;
char In[2020][2020];
pii pts[200020];
int idx[2020][2020], dis[2020][2020];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int pp[200020]; int Find(int x) { return pp[x] == x ? x : pp[x] = Find(pp[x]); }
vector <pii> E[200020];
int vis[200020], dep[200020];
int up[200020][20], upl[200020][20];

void dfs(int x, int fa, int cs) {
	vis[x] = cs;
	for(pii e : E[x]) if(e.Se != fa) {
		up[e.Se][0] = x; upl[e.Se][0] = e.Fi;
		for(int i=1;i<20;i++) {
			up[e.Se][i] = up[ up[e.Se][i-1] ][i-1];
			upl[e.Se][i] = max(upl[e.Se][i-1], upl[ up[e.Se][i-1] ][i-1]);
		}
		dep[e.Se] = dep[x] + 1;
		dfs(e.Se, x, cs);
	}
}

vector <t3> S;

int main() {
	scanf("%d%d%d%d", &H, &W, &P, &Q);
	for(int i=1;i<=H;i++) scanf("%s", In[i] + 1);
	memset(dis, -1, sizeof dis);
	vector <pii> q;
	for(int i=1;i<=P;i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		pts[i] = pii(x, y);
		idx[x][y] = i;
		dis[x][y] = 0;
		q.pb(pii(x, y));
	}
	auto add_edge = [&](int x, int y, int z) {
		S.pb(t3(z, x, y));
	};
	for(int i=1;i<=P;i++) pp[i] = i;
	rep(i, szz(q)) {
		pii t = q[i];
		rep(dir, 4) {
			int nx = t.Fi + dx[dir];
			int ny = t.Se + dy[dir];
			if(1 <= nx && nx <= H && 1 <= ny && ny <= W && In[nx][ny] != '#') {
				if(idx[nx][ny] == 0) {
					idx[nx][ny] = idx[t.Fi][t.Se];
					dis[nx][ny] = dis[t.Fi][t.Se] + 1;
					q.pb(pii(nx, ny));
				}
				else if(idx[t.Fi][t.Se] != idx[nx][ny]) {
					int a = idx[t.Fi][t.Se];
					int b = idx[nx][ny];
					add_edge(a, b, dis[t.Fi][t.Se] + dis[nx][ny]);
				}
			}
		}
	}
	sort(all(S));
	for(t3 e : S) {
		int z, x, y; tie(z, x, y) = e;
		
		x = Find(x), y = Find(y);
		if(x != y) E[x].pb(pii(z, y)), E[y].pb(pii(z, x)), pp[x] = y;
	}
	int cs = 0;
	for(int i=1;i<=P;i++) if(!vis[i]) dfs(i, -1, ++cs);
	rep(qq, Q) {
		int x, y;
		scanf("%d%d", &x, &y);
		if(vis[x] != vis[y]) puts("-1");
		else {
			int ans = 0;
			if(dep[y] > dep[x]) swap(x, y);
			rep(i, 20) if(1<<i & (dep[x] - dep[y])) {
				ans = max(ans, upl[x][i]);
				x = up[x][i];
			}
			for(int i=19;i>=0;i--) if(up[x][i] != up[y][i]) {
				ans = max({ans, upl[x][i], upl[y][i]});
				x = up[x][i], y = up[y][i];
			}
			if(x != y) ans = max({ans, upl[x][0], upl[y][0]});
			printf("%d\n", ans);
		}
	}
	return 0;
}

Compilation message

bottle.cpp: In function 'int main()':
bottle.cpp:59: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, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:60:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=H;i++) scanf("%s", In[i] + 1);
                        ~~~~~^~~~~~~~~~~~~~~~~
bottle.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
bottle.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21752 KB Output is correct
2 Correct 23 ms 22776 KB Output is correct
3 Correct 24 ms 22776 KB Output is correct
4 Correct 104 ms 24816 KB Output is correct
5 Correct 104 ms 24900 KB Output is correct
6 Correct 101 ms 24692 KB Output is correct
7 Correct 98 ms 24692 KB Output is correct
8 Correct 109 ms 25032 KB Output is correct
9 Correct 105 ms 24948 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 36588 KB Output is correct
2 Correct 62 ms 29156 KB Output is correct
3 Correct 336 ms 59048 KB Output is correct
4 Correct 488 ms 77184 KB Output is correct
5 Correct 515 ms 79296 KB Output is correct
6 Correct 309 ms 58932 KB Output is correct
7 Correct 458 ms 78916 KB Output is correct
8 Correct 525 ms 79292 KB Output is correct
9 Correct 589 ms 93168 KB Output is correct
10 Correct 338 ms 74940 KB Output is correct
11 Correct 409 ms 76220 KB Output is correct
12 Correct 191 ms 74060 KB Output is correct
13 Correct 224 ms 71356 KB Output is correct
14 Correct 181 ms 74168 KB Output is correct
15 Correct 223 ms 71484 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 36328 KB Output is correct
2 Correct 50 ms 28264 KB Output is correct
3 Correct 251 ms 61332 KB Output is correct
4 Correct 465 ms 80652 KB Output is correct
5 Correct 522 ms 83004 KB Output is correct
6 Correct 585 ms 97048 KB Output is correct
7 Correct 383 ms 78908 KB Output is correct
8 Correct 463 ms 82540 KB Output is correct
9 Correct 201 ms 78236 KB Output is correct
10 Correct 241 ms 75472 KB Output is correct
11 Correct 205 ms 57916 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 60496 KB Output is correct
2 Correct 977 ms 123932 KB Output is correct
3 Correct 356 ms 78912 KB Output is correct
4 Correct 1259 ms 136012 KB Output is correct
5 Correct 1518 ms 149656 KB Output is correct
6 Correct 656 ms 87656 KB Output is correct
7 Correct 359 ms 78820 KB Output is correct
8 Correct 153 ms 75452 KB Output is correct
9 Correct 1395 ms 149832 KB Output is correct
10 Correct 771 ms 109632 KB Output is correct
11 Correct 1212 ms 144448 KB Output is correct
12 Correct 981 ms 129792 KB Output is correct