oj.uz

Submission #478595

# Submission time Handle Problem Language Result Execution time Memory
478595 2021-10-08T04:20:46 Z sumit_kk10 물병 (JOI14_bottle) C++17
0 / 100
 5000 ms 53704 KB 
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 2005;
const int MOD = 1e9 + 7;
int n, m, p, q, ct, dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int component[N][N], dis[N][N];
char a[N][N];
bool vis[N][N];
bool pos[N][N];
pair<int, int> houses[N];

bool check(int i, int j){
    return (i >= 1 and i <= n and j >= 1 and j <= m and a[i][j] != '#' and !vis[i][j]);
}

bool check1(int i, int j){
    return (i >= 1 and i <= n and j >= 1 and j <= m and a[i][j] != '#');
}

void dfs(int i, int j, int x){
    component[i][j] = x;
    vis[i][j] = true;
    for(int k = 0; k < 4; ++k){
        int _i = i + dx[k], _j = j + dy[k];
        if(check(_i, _j))
            dfs(_i, _j, x);
    }
}

void solve(){
    cin >> n >> m >> p >> q;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            component[i][j] = ct;
            ++ct;
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> a[i][j];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(!vis[i][j])
                dfs(i, j, component[i][j]);
    for(int i = 1; i <= p; ++i){
        int u, v;
        cin >> u >> v;
        houses[i] = {u, v};
        pos[u][v] = true;
    }
    for(int i = 1; i <= q; ++i){
        int u, v;
        cin >> u >> v;
        if(component[houses[u].first][houses[u].second] != component[houses[v].first][houses[v].second]){
            cout << "-1\n";
            continue;
        }
        deque<pair<int, pair<int, pair<int, int> > > > q;
        q.push_back({0, {0, {houses[v].first, houses[v].second}}});
        for(int _i = 1; _i <= n; ++_i)
            for(int j = 1; j <= m; ++j)
                dis[_i][j] = INT_MAX;
        dis[houses[v].first][houses[v].second] = 0;
        int x = houses[u].first, y = houses[u].second;
        while(!q.empty()){
            int mx_cost = q.front().first, cost = q.front().second.first, _u = q.front().second.second.first, _v = q.front().second.second.second;
            q.pop_front();
            for(int k = 0; k < 4; ++k){
                int __u = _u + dx[k], __v = _v + dy[k];
                if(check1(__u, __v)){
                    if(pos[__u][__v] and dis[__u][__v] > max(mx_cost, cost + 1))
                        q.push_front({max(mx_cost, cost + 1), {0, {__u, __v}}});
                    else if(dis[__u][__v] > max(mx_cost, cost + 1))
                        q.push_back({max(mx_cost, cost + 1), {cost + 1, {__u, __v}}});
                    dis[__u][__v] = max(mx_cost, cost + 1);
                }
            }
        }
        cout << dis[x][y] - 1 << "\n";
    }
}

int main(){
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5089 ms 1736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5097 ms 31776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5092 ms 53704 KB Time limit exceeded
2 Halted 0 ms 0 KB -