제출 #5785

#제출 시각아이디문제언어결과실행 시간메모리
5785ainta물병 (JOI14_bottle)C++98
70 / 100
1788 ms97212 KiB
#pragma warning(disable:4996) #include<stdio.h> #include<algorithm> #include<queue> #include<vector> #define X first #define Y second #define W_ 2010 #define N_ 200010 #define INF 999999999 #define PII pair<int, int> using namespace std; int H, W, n, Query, D[W_][W_], P[W_][W_], cnt, par[N_], G[N_]; int pp[18][N_], LL[18][N_], Dep[N_]; vector<int>E[N_], L[N_]; priority_queue<PII>PQ; struct Edge{ int a, b, d; bool operator <(const Edge &p)const{ return d<p.d; } }tp; vector<Edge>Ed; char p[W_][W_]; void Do(int x, int y, int d, int pv){ if (D[x][y] <= 0 && G[P[x][y]] > d-1){ tp.a = pv, tp.b = P[x][y], tp.d = d - 1; Ed.push_back(tp); G[P[x][y]] = d - 1; cnt++; if(D[x][y] == -1)PQ.push(PII(0, x*(W + 1) + y)); D[x][y] = 0; } if (p[x][y] == '.' && D[x][y] > d){ P[x][y] = pv, D[x][y] = d; PQ.push(PII(-d, x*(W + 1) + y)); } } void BFS(int x, int y, int d) { if (d != D[x][y])return; d++; Do(x - 1, y, d, P[x][y]); Do(x + 1, y, d, P[x][y]); Do(x, y - 1, d, P[x][y]); Do(x, y + 1, d, P[x][y]); } int find(int a){ if (a == par[a])return a; return par[a] = find(par[a]); } void Connect(int a, int b, int d) { int x = find(a), y = find(b); if (x == y)return; E[a].push_back(b); L[a].push_back(d); E[b].push_back(a); L[b].push_back(d); par[x] = y; } void DFS(int a, int pa){ Dep[a] = Dep[pa] + 1; pp[0][a] = pa; int i; for (i = 0; i < E[a].size(); i++){ if (E[a][i] != pa){ DFS(E[a][i], a); LL[0][E[a][i]] = L[a][i]; } } } int Gap(int x, int y) { if (Dep[x] < Dep[y])return Gap(y, x); int d = Dep[x] - Dep[y], c = 0, r = 0, i; while (d){ if (d & 1){ r = max(r, LL[c][x]); x = pp[c][x]; } c++; d >>= 1; } for (i = 17; i >= 0; i--){ if (pp[i][x] != pp[i][y]){ r = max(r, max(LL[i][x], LL[i][y])); x = pp[i][x], y = pp[i][y]; } } if (x != y){ r = max(r, max(LL[0][x], LL[0][y])); x = pp[0][x], y = pp[0][y]; } if (!x)return -1; return r; } int main() { int i, j, x, y; PII t; scanf("%d%d%d%d", &H, &W, &n, &Query); for (i = 1; i <= H; i++){ scanf("%s", p[i] + 1); for (j = 1; j <= W; j++){ D[i][j] = INF; } } for (i = 1; i <= n; i++){ scanf("%d%d", &x, &y); D[x][y] = -1, P[x][y] = i; par[i] = i; G[i] = INF; } for (i = 1; i <= H; i++){ for (j = 1; j <= W; j++){ if (D[i][j] == -1){ D[i][j] = 0; G[P[i][j]] = 0; PQ.push(PII(0, i*(W + 1) + j)); while (!PQ.empty()){ t = PQ.top(); PQ.pop(); BFS(t.Y / (W + 1), t.Y % (W + 1), -t.X); } } } } sort(Ed.begin(), Ed.end()); for (i = 0; i != Ed.size(); i++){ Connect(Ed[i].a, Ed[i].b, Ed[i].d); } for (i = 1; i <= n; i++){ if (!pp[0][i])DFS(i, 0); } for (i = 1; i < 18; i++){ for (j = 1; j <= n; j++){ pp[i][j] = pp[i - 1][pp[i - 1][j]]; LL[i][j] = max(LL[i - 1][j], LL[i - 1][pp[i - 1][j]]); } } while (Query--) { scanf("%d%d", &x, &y); printf("%d\n", Gap(x, y)); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...