oj.uz

Submission #5704

# Submission time Handle Problem Language Result Execution time Memory
5704 2014-05-14T04:48:54 Z cki86201 물병 (JOI14_bottle) C++
30 / 100
 808 ms 138284 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;

#define X first
#define Y second
typedef pair<int,int> Pi;

int H, W, P, Q;
char ch[2020][2020];
Pi inp[200020];
int Que[2002*2002];
int wh[2002*2002], di[2002*2002];
Pi vec[2002*2002];
int topv;
bool chk[2002*2002];
int xx[4] = {0, 1, 0, -1}, yy[4] = {1, 0, -1, 0};
int st[200020], en[400040], nxt[400040], len[400040];
inline void addE(int s,int e,int c,int l){nxt[c]=st[s],st[s]=c,en[c]=e,len[c]=l;}
inline void add(int s,int e,int &c,int l){addE(s,e,++c,l);addE(e,s,++c,l);}
struct edge{
	edge(){}
	edge(int s,int e,int l):s(s),e(e),l(l){}
	int s, e, l;
	bool operator<(const edge &a)const{
		return l<a.l;
	}
}E[1000010];
int top;

struct unf{
	static const int N_ = 200020;
	unf(){for(int i=0;i<N_;i++)p[i] = i, w[i] = 1;}
	int p[N_], w[N_];
	int Find(int x){
		if(p[x] == x)return x;
		return p[x] = Find(p[x]);
	}
	bool Union(int x,int y){
		x = Find(x), y = Find(y);
		if(x == y)return false;
		if(w[x] > w[y])w[x] += w[y], p[y] = x;
		else w[y] += w[x], p[x] = y;
		return true;
	}
	bool chk(int x,int y){return Find(x) == Find(y);}
}uf;

int up[200020][18];
int mx[200020][18];
int dep[200020];
bool vis[200020];

void dfs(int x)
{
	vis[x] = 1;
	for(int i=st[x];i;i=nxt[i])
		if(!vis[en[i]]){
			dep[en[i]] = dep[x] + 1;
			up[en[i]][0] = x;
			mx[en[i]][0] = len[i];
			for(int j=1;j<18;j++){
				up[en[i]][j] = up[ up[en[i]][j-1] ][j-1];
				mx[en[i]][j] = max(mx[en[i]][j-1], mx[up[en[i]][j-1]][j-1]);
			}
			dfs(en[i]);
		}
}

int Get(int x,int y)
{
	if(dep[x] < dep[y])swap(x,y);
	int res = 0;
	for(int i=0;i<18;i++){
		if(1<<i&(dep[x]-dep[y]))res = max(res, mx[x][i]), x = up[x][i];
	}
	if(x == y)return res;
	for(int i=17;i;i--)
		if(up[x][i] != up[y][i]){
			res = max(res, mx[x][i]);
			res = max(res, mx[y][i]);
			x = up[x][i], y = up[y][i];
		}
	return max(res, max(mx[y][0], mx[x][0]));
}

int main()
{
	scanf("%d%d%d%d",&H,&W,&P,&Q);
	int i;
	for(i=0;i<H;i++)scanf("%s",ch[i]);
	int *fr = Que, *re = Que;
	for(i=1;i<=P;i++){
		scanf("%d%d",&inp[i].X,&inp[i].Y);
		--inp[i].X; --inp[i].Y;
		int a = inp[i].X * W + inp[i].Y;
		*fr++ = a; wh[a] = i; chk[a] = 1;
	}
	int now = 0;
	while(fr != re){
		int t = *re++;
		if(di[t] != now){
			now = di[t];
			while(topv--)uf.Union(vec[topv].X, vec[topv].Y);
			topv = 0;
		}
		for(i=0;i<4;i++){
			int tx = t/W + xx[i];
			int ty = t%W + yy[i];
			if(tx < 0 || tx >= H || ty < 0 || ty >= W || ch[tx][ty] == '#')continue;
			int nex = tx*W+ty;
			if(!chk[nex]){
				*fr++ = nex;
				di[nex] = di[t] + 1;
				wh[nex] = wh[t];
				chk[nex] = 1;
			}
			if(chk[nex] && uf.chk(wh[nex], wh[t]))continue;
			if(chk[nex])E[top++] = edge(wh[nex], wh[t], di[t] + di[nex]), vec[topv++] = Pi(wh[nex], wh[t]);
		}
	}
	sort(E, E+top);
	uf = unf();
	int c_edge = 2;
	for(i=0;i<top;i++)if(uf.Union(E[i].s, E[i].e))add(E[i].s, E[i].e, c_edge, E[i].l);
	for(i=1;i<=P;i++)if(!vis[i])dfs(i);
	for(int tt=1;tt<=Q;tt++){
		int x, y;
		scanf("%d%d",&x,&y);
		if(!uf.chk(x,y))printf("-1\n");
		else printf("%d\n",Get(x,y));
	}
	return 0;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 138128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 138132 KB Output is correct
2 Correct 48 ms 138140 KB Output is correct
3 Correct 432 ms 138132 KB Output is correct
4 Correct 632 ms 138136 KB Output is correct
5 Correct 708 ms 138136 KB Output is correct
6 Correct 420 ms 138136 KB Output is correct
7 Correct 624 ms 138132 KB Output is correct
8 Correct 704 ms 138144 KB Output is correct
9 Correct 808 ms 138132 KB Output is correct
10 Correct 476 ms 138128 KB Output is correct
11 Correct 560 ms 138132 KB Output is correct
12 Correct 188 ms 138140 KB Output is correct
13 Correct 320 ms 138276 KB Output is correct
14 Correct 188 ms 138136 KB Output is correct
15 Correct 300 ms 138284 KB Output is correct

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 138136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 600 ms 138136 KB Output isn't correct
2 Halted 0 ms 0 KB -