oj.uz

Submission #500002

# Submission time Handle Problem Language Result Execution time Memory
500002 2021-12-30T09:09:05 Z Nartifact Mecho (IOI09_mecho) C++14
9 / 100
 228 ms 65540 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define pii pair <int,int>
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int N = 888, inf = 1e15;
const int H[] = {1, 0, -1, 0};
const int C[] = {0, 1, 0, -1};
int n, s, cti = inf;
char a[N][N];
int t[N][N], mec[N][N];
pii sta, fin;

bool valid (const int& x, const int& y)
{
    return x && y && x <= n && y <= n
          && a[x][y] != 'T';
}

bool ok (const int& tg)
{
    queue <pii> q;
    q.push(sta);
    forinc(i,1,n) forinc(j,1,n) mec[i][j] = inf;
    mec[sta.fi][sta.se] = 0;
    while(q.size()) {
        auto x = q.front(); q.pop();
        if(x == fin) return 1;
        forinc(i,0,3) {
            int nh = x.fi + H[i];
            int nc = x.se + C[i];
            if(valid(nh, nc) && (mec[x.fi][x.se] + 1) / s <= t[nh][nc] - tg) {
                mec[nh][nc] = mec[x.fi][x.se] + 1;
                q.push({nh, nc});
            }
        }
    }
    return 0;
}

void solve ()
{
    queue <pii> q;
    forinc(i,1,n) forinc(j,1,n){
        t[i][j] = inf;
        if(a[i][j] == 'H') {
            q.push({i, j});
            t[i][j] = 0;
        }
        else if(a[i][j] == 'M') {
            sta = {i, j};
            t[i][j] = -1;
        }
        else if(a[i][j] == 'D')
            fin = {i, j};
    }

    // bfs bee
    int last = 0;
    while(q.size()) {
        auto x = q.front(); q.pop();
        forinc(i,0,3) {
            int nh = x.fi + H[i];
            int nc = x.se + C[i];
            if(valid(nh, nc) && t[nh][nc] > t[x.fi][x.se] + 1) {
                t[nh][nc] = t[x.fi][x.se] + 1;
                last = max(last, t[nh][nc]);
                q.push({nh, nc});
            }
        }
    }

    // binary search
    int l = 0, r = last, ans = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(ok(mid)) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    if(ans == -1) cout << ans;
    else cout << ans - 1;
}

void read ()
{
    cin >> n >> s;
    forinc(i,1,n) forinc(j,1,n)
        cin >> a[i][j];
    solve();
}

main ()
{
	#define task "ioi09_mecho"
	cin.tie(0) -> sync_with_stdio(0);
	if(fopen (task ".inp", "r")) {
		freopen (task ".inp", "r", stdin);
		freopen (task ".out", "w", stdout);
	}
    read();
	return 0;
}

Compilation message

mecho.cpp: In function 'void solve()':
mecho.cpp:86:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int mid = l + r >> 1;
      |                   ~~^~~
mecho.cpp: At global scope:
mecho.cpp:105:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  105 | main ()
      | ^~~~
mecho.cpp: In function 'int main()':
mecho.cpp:110:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |   freopen (task ".inp", "r", stdin);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:111:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   freopen (task ".out", "w", stdout);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 0 ms 312 KB Output isn't correct
5 Correct 1 ms 460 KB Output is correct
6 Runtime error 191 ms 65540 KB Execution killed with signal 9
7 Runtime error 114 ms 65540 KB Execution killed with signal 9
8 Correct 1 ms 448 KB Output is correct
9 Correct 62 ms 30644 KB Output is correct
10 Correct 18 ms 4284 KB Output is correct
11 Correct 3 ms 972 KB Output is correct
12 Runtime error 148 ms 65540 KB Execution killed with signal 9
13 Runtime error 112 ms 65540 KB Execution killed with signal 9
14 Runtime error 107 ms 65540 KB Execution killed with signal 9
15 Runtime error 228 ms 65540 KB Execution killed with signal 9
16 Runtime error 200 ms 65540 KB Execution killed with signal 9
17 Runtime error 153 ms 65540 KB Execution killed with signal 9
18 Runtime error 150 ms 65540 KB Execution killed with signal 9
19 Runtime error 228 ms 65540 KB Execution killed with signal 9
20 Runtime error 158 ms 65540 KB Execution killed with signal 9
21 Runtime error 152 ms 65540 KB Execution killed with signal 9
22 Runtime error 142 ms 65540 KB Execution killed with signal 9
23 Runtime error 153 ms 65540 KB Execution killed with signal 9
24 Runtime error 140 ms 65540 KB Execution killed with signal 9
25 Runtime error 141 ms 65540 KB Execution killed with signal 9
26 Runtime error 148 ms 65540 KB Execution killed with signal 9
27 Runtime error 147 ms 65540 KB Execution killed with signal 9
28 Runtime error 148 ms 65540 KB Execution killed with signal 9
29 Runtime error 144 ms 65540 KB Execution killed with signal 9
30 Runtime error 156 ms 65540 KB Execution killed with signal 9
31 Runtime error 149 ms 65536 KB Execution killed with signal 9
32 Runtime error 147 ms 65540 KB Execution killed with signal 9
33 Runtime error 143 ms 65540 KB Execution killed with signal 9
34 Runtime error 141 ms 65536 KB Execution killed with signal 9
35 Runtime error 130 ms 65540 KB Execution killed with signal 9
36 Runtime error 140 ms 65540 KB Execution killed with signal 9
37 Runtime error 141 ms 65540 KB Execution killed with signal 9
38 Runtime error 128 ms 65540 KB Execution killed with signal 9
39 Runtime error 137 ms 65540 KB Execution killed with signal 9
40 Runtime error 136 ms 65540 KB Execution killed with signal 9
41 Runtime error 128 ms 65540 KB Execution killed with signal 9
42 Runtime error 137 ms 65536 KB Execution killed with signal 9
43 Runtime error 139 ms 65536 KB Execution killed with signal 9
44 Runtime error 130 ms 65540 KB Execution killed with signal 9
45 Runtime error 154 ms 65540 KB Execution killed with signal 9
46 Runtime error 137 ms 65540 KB Execution killed with signal 9
47 Runtime error 128 ms 65540 KB Execution killed with signal 9
48 Runtime error 142 ms 65540 KB Execution killed with signal 9
49 Runtime error 144 ms 65540 KB Execution killed with signal 9
50 Runtime error 131 ms 65540 KB Execution killed with signal 9
51 Runtime error 142 ms 65540 KB Execution killed with signal 9
52 Runtime error 144 ms 65540 KB Execution killed with signal 9
53 Runtime error 130 ms 65540 KB Execution killed with signal 9
54 Runtime error 142 ms 65540 KB Execution killed with signal 9
55 Runtime error 140 ms 65540 KB Execution killed with signal 9
56 Runtime error 134 ms 65540 KB Execution killed with signal 9
57 Runtime error 138 ms 65540 KB Execution killed with signal 9
58 Runtime error 141 ms 65540 KB Execution killed with signal 9
59 Runtime error 142 ms 65540 KB Execution killed with signal 9
60 Runtime error 144 ms 65540 KB Execution killed with signal 9
61 Runtime error 142 ms 65540 KB Execution killed with signal 9
62 Runtime error 136 ms 65540 KB Execution killed with signal 9
63 Runtime error 140 ms 65540 KB Execution killed with signal 9
64 Runtime error 149 ms 65540 KB Execution killed with signal 9
65 Runtime error 150 ms 65540 KB Execution killed with signal 9
66 Runtime error 145 ms 65540 KB Execution killed with signal 9
67 Runtime error 141 ms 65540 KB Execution killed with signal 9
68 Runtime error 153 ms 65540 KB Execution killed with signal 9
69 Runtime error 150 ms 65540 KB Execution killed with signal 9
70 Runtime error 157 ms 65540 KB Execution killed with signal 9
71 Runtime error 148 ms 65540 KB Execution killed with signal 9
72 Runtime error 147 ms 65540 KB Execution killed with signal 9
73 Runtime error 112 ms 65540 KB Execution killed with signal 9
74 Runtime error 123 ms 65540 KB Execution killed with signal 9
75 Runtime error 115 ms 65540 KB Execution killed with signal 9
76 Runtime error 114 ms 65540 KB Execution killed with signal 9
77 Runtime error 118 ms 65540 KB Execution killed with signal 9
78 Runtime error 116 ms 65540 KB Execution killed with signal 9
79 Runtime error 113 ms 65540 KB Execution killed with signal 9
80 Runtime error 117 ms 65540 KB Execution killed with signal 9
81 Runtime error 117 ms 65540 KB Execution killed with signal 9
82 Runtime error 117 ms 65540 KB Execution killed with signal 9
83 Runtime error 113 ms 65540 KB Execution killed with signal 9
84 Runtime error 114 ms 65540 KB Execution killed with signal 9
85 Runtime error 114 ms 65540 KB Execution killed with signal 9
86 Runtime error 110 ms 65540 KB Execution killed with signal 9
87 Runtime error 112 ms 65540 KB Execution killed with signal 9
88 Runtime error 111 ms 65540 KB Execution killed with signal 9
89 Runtime error 116 ms 65540 KB Execution killed with signal 9
90 Runtime error 113 ms 65540 KB Execution killed with signal 9
91 Runtime error 119 ms 65540 KB Execution killed with signal 9
92 Runtime error 113 ms 65540 KB Execution killed with signal 9