oj.uz

Submission #62896

# Submission time Handle Problem Language Result Execution time Memory
62896 2018-07-30T17:38:19 Z kdh9949 물병 (JOI14_bottle) C++17
0 / 100
 825 ms 327664 KB 
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
#define X first
#define Y second

#define pb push_back

const int H = 3005, N = 200005, lgN = 18, dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

int h, w, n, m, p[N], q[N], c, s[2 * N][lgN + 1], v[2 * N], r[2 * N];
char a[H][H];
pii b[N], d[H][H];
queue<pii> Q;
vector<int> t[2 * N];
vector<pii> e[H * H];

int f(int x){ return p[x] = (x == p[x] ? x : f(p[x])); }

void u(int x, int y, int z){
    x = f(x); y = f(y);
    if(x == y) return;
    s[q[x]][0] = s[q[y]][0] = ++c;
    t[c].pb(q[x]); t[c].pb(q[y]);
    v[c] = z;
    q[x] = c;
    p[y] = x;
}

void g(int x){
    for(int i = 1; i <= lgN; i++) s[x][i] = s[s[x][i - 1]][i - 1];
    for(int i : t[x]){
        r[i] = r[x] + 1;
        g(i);
    }
}

int l(int x, int y){
    if(r[x] < r[y]) swap(x, y);
    for(int i = lgN; ~i; i--) if(r[x] - (1 << i) >= r[y]) x = s[x][i];
    if(x == y) return x;
    for(int i = lgN; ~i; i--) if(s[x][i] != s[y][i]){ x = s[x][i]; y = s[y][i]; }
    return s[x][0];
}

int main(){
    scanf("%d%d%d%d", &h, &w, &n, &m);
    for(int i = 1; i <= h; i++) scanf("%s", a[i] + 1);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &b[i].X, &b[i].Y);
        d[b[i].X][b[i].Y] = {i, 0};
        Q.push(b[i]);
    }
    while(!Q.empty()){
        pii z = Q.front(); Q.pop();
        for(int i = 0; i < 4; i++){
            int x = z.X + dx[i], y = z.Y + dy[i];
            if(a[x][y] == '.' && !d[x][y].X){
                d[x][y] = {d[z.X][z.Y].X, d[z.X][z.Y].Y + 1};
                Q.push({x, y});
            }
        }
    }
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            if(!d[i][j].X) continue;
            for(int k = 0; k < 4; k++){
                int x = i + dx[k], y = j + dy[k];
                if(d[x][y].X && d[i][j].X != d[x][y].X)
                    e[d[i][j].Y + d[x][y].Y].pb({d[i][j].X, d[x][y].X});
            }
        }
    }
    iota(p, p + n + 1, 0);
    iota(q, q + n + 1, 0);
    c = n;
    for(int i = 1; i <= w * h; i++) for(auto &j : e[i]) u(j.X, j.Y, i);
    for(int i = n + 1; i <= c; i++) if(!s[i][0]) g(i);
    v[0] = -1;
    for(int x, y; m--; ){
        scanf("%d%d", &x, &y);
        printf("%d\n", v[l(x, y)]);
    }
}

Compilation message

bottle.cpp: In function 'int main()':
bottle.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &h, &w, &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:49:38: 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", a[i] + 1);
                                 ~~~~~^~~~~~~~~~~~~~~~
bottle.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &b[i].X, &b[i].Y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 238176 KB Output is correct
2 Correct 287 ms 238176 KB Output is correct
3 Correct 654 ms 273236 KB Output is correct
4 Correct 770 ms 278908 KB Output is correct
5 Correct 771 ms 284804 KB Output is correct
6 Correct 577 ms 285152 KB Output is correct
7 Correct 666 ms 290864 KB Output is correct
8 Correct 731 ms 296632 KB Output is correct
9 Correct 731 ms 303616 KB Output is correct
10 Correct 698 ms 303616 KB Output is correct
11 Correct 696 ms 305304 KB Output is correct
12 Correct 386 ms 305304 KB Output is correct
13 Correct 432 ms 305304 KB Output is correct
14 Correct 378 ms 306672 KB Output is correct
15 Incorrect 482 ms 308580 KB Output isn't correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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