Submission #62898

#	Time	Username	Problem	Language	Result	Execution time	Memory
62898		kdh9949	물병 (JOI14_bottle)	C++17	100 / 100	1530 ms	428144 KiB

bottle

#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 = 0; 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 (stderr)

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: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30