oj.uz

Submission #62898

# Submission time Handle Problem Language Result Execution time Memory
62898 2018-07-30T17:39:50 Z kdh9949 물병 (JOI14_bottle) C++17
100 / 100
 1530 ms 428144 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 = 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 222384 KB Output is correct
2 Correct 219 ms 223704 KB Output is correct
3 Correct 212 ms 223864 KB Output is correct
4 Correct 333 ms 225992 KB Output is correct
5 Correct 339 ms 227520 KB Output is correct
6 Correct 338 ms 228732 KB Output is correct
7 Correct 326 ms 230172 KB Output is correct
8 Correct 329 ms 231920 KB Output is correct
9 Correct 297 ms 233220 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 246756 KB Output is correct
2 Correct 271 ms 246756 KB Output is correct
3 Correct 712 ms 278260 KB Output is correct
4 Correct 715 ms 279936 KB Output is correct
5 Correct 761 ms 282008 KB Output is correct
6 Correct 713 ms 282008 KB Output is correct
7 Correct 903 ms 282008 KB Output is correct
8 Correct 844 ms 282028 KB Output is correct
9 Correct 1025 ms 284896 KB Output is correct
10 Correct 733 ms 284896 KB Output is correct
11 Correct 710 ms 284896 KB Output is correct
12 Correct 353 ms 284896 KB Output is correct
13 Correct 423 ms 284896 KB Output is correct
14 Correct 415 ms 284896 KB Output is correct
15 Correct 495 ms 284896 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 284896 KB Output is correct
2 Correct 281 ms 284896 KB Output is correct
3 Correct 571 ms 284896 KB Output is correct
4 Correct 698 ms 288596 KB Output is correct
5 Correct 809 ms 294712 KB Output is correct
6 Correct 852 ms 301836 KB Output is correct
7 Correct 705 ms 301836 KB Output is correct
8 Correct 719 ms 304860 KB Output is correct
9 Correct 380 ms 304860 KB Output is correct
10 Correct 425 ms 304860 KB Output is correct
11 Correct 455 ms 304860 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 316944 KB Output is correct
2 Correct 1319 ms 366956 KB Output is correct
3 Correct 626 ms 366956 KB Output is correct
4 Correct 1437 ms 385760 KB Output is correct
5 Correct 1444 ms 400124 KB Output is correct
6 Correct 907 ms 400124 KB Output is correct
7 Correct 699 ms 400124 KB Output is correct
8 Correct 405 ms 400124 KB Output is correct
9 Correct 1355 ms 420060 KB Output is correct
10 Correct 1084 ms 420060 KB Output is correct
11 Correct 1530 ms 428144 KB Output is correct
12 Correct 1285 ms 428144 KB Output is correct