oj.uz

Submission #1098026

# Submission time Handle Problem Language Result Execution time Memory
1098026 2024-10-08T20:09:11 Z vjudge1 Mecho (IOI09_mecho) C++17
4 / 100
 4 ms 2176 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef local
  #include "debug.hpp"
  #define pr(...) debug(#__VA_ARGS__, __VA_ARGS__)
  #define prs(...) debug_nameless(__VA_ARGS__)
#else
  #define pr(...) 69
  #define prs(...) 69
#endif

#define endl '\n'

const int inf = 1e9;
const long long binf = 1e18;

void solve(int tc){
  int n, s;
  cin >> n >> s;
  int st = -1, ed = -1;
  vector <int> bees;
  auto get_hash = [&](int i, int j){
    return n*i + j;
  };
  vector <string> grid(n);
  for(int i = 0; i < n; i++){
    cin >> grid[i];
    for(int j = 0; j < n; j++){
      int hash = get_hash(i, j);
      if(grid[i][j] == 'M') st = hash;
      if(grid[i][j] == 'D') ed = hash;
      if(grid[i][j] == 'H') bees.push_back(hash);
    }
  }
  assert(bees.size() > 0 && st != -1 && ed != -1);
  auto check = [&](long long t){
    vector <vector<long long>> bdist(n, vector<long long>(n, binf));
    queue <int> queue;
    for(int b : bees){
      queue.push(b);
      bdist[b/n][b%n] = 0;
    }
    auto inside = [&](int l, int c){
      return (min(l, c) >= 0 && max(l, c) < n && (grid[l][c] == 'G' || grid[l][c] == 'D' || grid[l][c] == 'M'));
    };
    while(queue.size() > 0){
      int node = queue.front();
      queue.pop();
      int l = node/n, c = node%n;
      for(int i = -1; i <= 1; i++){
        for(int j = -1; j <= 1; j++){
          if(i*j != 0) continue;
          int delta = (bdist[l][c] < t ? 1 : s);
          if(inside(l+i, c+j) && grid[l+i][c+j] != 'D' && bdist[l+i][c+j] > delta + bdist[l][c]){
            queue.push(get_hash(l+i, c+j));
            bdist[l+i][c+j] = delta + bdist[l][c];
          }
        }
      }
    }
    while(queue.size()) queue.pop();
    vector <vector<long long>> dist(n, vector<long long>(n, binf));
    dist[st/n][st%n] = t;
    if(bdist[st/n][st%n] <= dist[st/n][st%n]) return false;
    queue.push(st);
    while(queue.size() > 0){
      int node = queue.front();
      queue.pop();
      int l = node/n, c = node%n;
      for(int i = -1; i <= 1; i++){
        for(int j = -1; j <= 1; j++){
          if(i*j != 0) continue;
          if(inside(l+i, c+j) && bdist[l+i][c+j] > 1 + dist[l][c] && 1+dist[l][c] < dist[l+i][c+j]){
            queue.push(get_hash(l+i, c+j));
            dist[l+i][c+j] = 1 + dist[l][c];
          }
        }
      }
    }
    int l = ed/n, c = ed%n;
    for(int i = -1; i <= 1; i++){
      for(int j = -1; j <= 1; j++){
        if(i*j != 0) continue;
        if(inside(l+i, c+j) && dist[l+i][c+j] < bdist[l+i][c+j]){
          return true;
        }
      }
    }
    return false;
  };
  long long l, r = 1e15;
  long long ans = -1;
  while(0 && l <= r){
    long long mid = (l + r)/2;
    if(check(mid)){
      l = mid+1;
      ans = mid;
    }else{
      r = mid-1;
    }
  }
  cout << ans << endl;
}  

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0);

  int tt = 1;
  while(tt--){
    prs(string(50, '-'));
    solve(tt);
    prs(string(50, '-'));
  }

  return 0;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 |   #define prs(...) 69
      |                    ^~
mecho.cpp:111:5: note: in expansion of macro 'prs'
  111 |     prs(string(50, '-'));
      |     ^~~
mecho.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 |   #define prs(...) 69
      |                    ^~
mecho.cpp:113:5: note: in expansion of macro 'prs'
  113 |     prs(string(50, '-'));
      |     ^~~

Subtask #1
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 2 ms 1624 KB Output isn't correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Incorrect 0 ms 456 KB Output isn't correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Incorrect 0 ms 600 KB Output isn't correct
14 Correct 1 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Incorrect 0 ms 452 KB Output isn't correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Incorrect 0 ms 348 KB Output isn't correct
22 Incorrect 0 ms 348 KB Output isn't correct
23 Incorrect 1 ms 456 KB Output isn't correct
24 Incorrect 0 ms 604 KB Output isn't correct
25 Incorrect 0 ms 452 KB Output isn't correct
26 Incorrect 1 ms 344 KB Output isn't correct
27 Incorrect 1 ms 344 KB Output isn't correct
28 Incorrect 0 ms 348 KB Output isn't correct
29 Incorrect 0 ms 348 KB Output isn't correct
30 Incorrect 0 ms 348 KB Output isn't correct
31 Incorrect 0 ms 348 KB Output isn't correct
32 Incorrect 0 ms 348 KB Output isn't correct
33 Incorrect 1 ms 676 KB Output isn't correct
34 Incorrect 1 ms 604 KB Output isn't correct
35 Incorrect 1 ms 600 KB Output isn't correct
36 Incorrect 1 ms 604 KB Output isn't correct
37 Incorrect 1 ms 604 KB Output isn't correct
38 Incorrect 1 ms 604 KB Output isn't correct
39 Incorrect 1 ms 860 KB Output isn't correct
40 Incorrect 1 ms 856 KB Output isn't correct
41 Incorrect 1 ms 860 KB Output isn't correct
42 Incorrect 1 ms 860 KB Output isn't correct
43 Incorrect 1 ms 860 KB Output isn't correct
44 Incorrect 1 ms 840 KB Output isn't correct
45 Incorrect 1 ms 860 KB Output isn't correct
46 Incorrect 1 ms 860 KB Output isn't correct
47 Incorrect 1 ms 860 KB Output isn't correct
48 Incorrect 1 ms 1116 KB Output isn't correct
49 Incorrect 1 ms 1116 KB Output isn't correct
50 Incorrect 2 ms 1116 KB Output isn't correct
51 Incorrect 2 ms 1116 KB Output isn't correct
52 Incorrect 1 ms 1116 KB Output isn't correct
53 Incorrect 1 ms 1116 KB Output isn't correct
54 Incorrect 2 ms 1372 KB Output isn't correct
55 Incorrect 2 ms 1372 KB Output isn't correct
56 Incorrect 2 ms 1280 KB Output isn't correct
57 Incorrect 2 ms 1372 KB Output isn't correct
58 Incorrect 3 ms 1372 KB Output isn't correct
59 Incorrect 2 ms 1372 KB Output isn't correct
60 Incorrect 3 ms 1636 KB Output isn't correct
61 Incorrect 2 ms 1628 KB Output isn't correct
62 Incorrect 2 ms 1628 KB Output isn't correct
63 Incorrect 2 ms 1628 KB Output isn't correct
64 Incorrect 2 ms 1628 KB Output isn't correct
65 Incorrect 2 ms 1580 KB Output isn't correct
66 Incorrect 2 ms 1532 KB Output isn't correct
67 Correct 2 ms 1624 KB Output is correct
68 Incorrect 2 ms 1416 KB Output isn't correct
69 Incorrect 2 ms 1628 KB Output isn't correct
70 Incorrect 2 ms 1556 KB Output isn't correct
71 Incorrect 2 ms 1628 KB Output isn't correct
72 Incorrect 2 ms 1524 KB Output isn't correct
73 Incorrect 2 ms 1484 KB Output isn't correct
74 Incorrect 2 ms 1624 KB Output isn't correct
75 Incorrect 3 ms 1628 KB Output isn't correct
76 Incorrect 4 ms 1624 KB Output isn't correct
77 Incorrect 3 ms 1668 KB Output isn't correct
78 Correct 2 ms 1624 KB Output is correct
79 Incorrect 2 ms 1628 KB Output isn't correct
80 Incorrect 2 ms 1628 KB Output isn't correct
81 Incorrect 2 ms 1492 KB Output isn't correct
82 Incorrect 2 ms 1628 KB Output isn't correct
83 Incorrect 2 ms 1540 KB Output isn't correct
84 Incorrect 2 ms 1668 KB Output isn't correct
85 Incorrect 3 ms 1628 KB Output isn't correct
86 Incorrect 2 ms 1628 KB Output isn't correct
87 Incorrect 2 ms 1676 KB Output isn't correct
88 Incorrect 4 ms 2176 KB Output isn't correct
89 Incorrect 3 ms 1508 KB Output isn't correct
90 Incorrect 2 ms 1628 KB Output isn't correct
91 Incorrect 2 ms 1628 KB Output isn't correct
92 Incorrect 2 ms 1628 KB Output isn't correct