| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 5772 |
2014-05-17T06:57:32 Z |
ainta |
물병 (JOI14_bottle) |
C++ |
|
96 ms |
170608 KB |
#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_];
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;
}
}Ed[W_*W_*2];
char p[W_][W_];
void Do(int x, int y, int d, int pv){
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);
PQ.push(PII(0,x*(W + 1) + y));
D[x][y] = 0, P[x][y] = i;
par[i] = i;
}
while (!PQ.empty()){
t = PQ.top();
PQ.pop();
BFS(t.Y / (W + 1), t.Y % (W + 1), -t.X);
}
for (i = 1; i <= n; i++){
for (j = 1; j <= n; j++){
if (P[i][j] && P[i][j + 1] && P[i][j] != P[i][j + 1]){
Ed[cnt].a = P[i][j], Ed[cnt].b = P[i][j + 1], Ed[cnt].d = D[i][j] + D[i][j + 1];
cnt++;
}
if (P[i][j] && P[i + 1][j] && P[i][j] != P[i + 1][j]){
Ed[cnt].a = P[i][j], Ed[cnt].b = P[i + 1][j], Ed[cnt].d = D[i][j] + D[i + 1][j];
cnt++;
}
}
}
sort(Ed, Ed + cnt);
for (i = 0; i < cnt; 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 time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
170476 KB |
Output is correct |
| 2 |
Correct |
4 ms |
170476 KB |
Output is correct |
| 3 |
Correct |
8 ms |
170476 KB |
Output is correct |
| 4 |
Correct |
96 ms |
170476 KB |
Output is correct |
| 5 |
Correct |
84 ms |
170476 KB |
Output is correct |
| 6 |
Correct |
92 ms |
170476 KB |
Output is correct |
| 7 |
Correct |
92 ms |
170476 KB |
Output is correct |
| 8 |
Correct |
92 ms |
170476 KB |
Output is correct |
| 9 |
Correct |
92 ms |
170476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
170608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
170608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
-1: Interrupted system call |
| 2 |
Halted |
0 ms |
0 KB |
- |
