oj.uz

Submission #484408

# Submission time Handle Problem Language Result Execution time Memory
484408 2021-11-03T09:08:56 Z Dirii Mecho (IOI09_mecho) C++14
15 / 100
 1000 ms 65540 KB 
// #pragma GCC target("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define cll const ll
#define lp(a, b, c) for(ll a = b; a <= c; ++a)
#define lpd(a, b, c) for(ll a = b; a >= c; --a)
#define vec(a) vector<a>
#define pp(a, b) pair<a, b>
#define EACHCASE lpd(cs, read(), 1)
#define Fname "mecho"
using namespace std;

template <typename T> inline void Read(T &x){
    x = 0; char c;
    ll dau = 1;
    while(!isdigit(c = getchar())) if(c == '-') dau = -1;
    do{
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
    x *= dau;
}

ll read(){
    ll tmp;
    cin >> tmp;
    return tmp;
}

void giuncute(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}

void OF(){
    if(fopen(Fname".inp", "r")){
        freopen(Fname".inp", "r", stdin);
        freopen(Fname".out", "w", stdout);
    } else if(fopen(Fname".in", "r")){
        freopen(Fname".in", "r", stdin);
        freopen(Fname".out", "w", stdout);
    }
}

cll mxn = 805, dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
ll n, s, a[mxn][mxn], d[mxn][mxn];
pp(ll, ll) st, fi;
queue<pp(ll, ll)> q;

void bfs(ll i, ll j, ll step, const ll &ti){
    // if(step == s) return;
    // lp(t, 0, 3){
    //     ll ii = i + dx[t], jj = j + dy[t];
    //     if(a[ii][jj] == -1 || d[ii][jj]) continue;
    //     d[ii][jj] = ti;
    //     if(a[ii][jj] > ti) q.push({ii, jj});
    //     dfs(ii, jj, step + 1, ti);
    // }
    queue<pp(ll, ll)> qq[2];
    qq[0].push({i, j});
    while(qq[0].size()){
        if(++step > s) break;
        while(qq[0].size()){
            ll u = qq[0].front().first, v = qq[0].front().second;
            // if(i == 4 && j == 5) cerr << u << ' ' << v << '\n';
            qq[0].pop();
            lp(t, 0, 3){
                ll nu = u + dx[t], nv = v + dy[t];
                if(a[nu][nv] == -1 || (d[nu][nv] != d[u][v] && d[nu][nv] != 0)) continue;
                d[nu][nv] = d[u][v];
                if(a[nu][nv] > d[nu][nv]) q.push({nu, nv});
                qq[1].push({nu, nv});
            }
        }
        swap(qq[0], qq[1]);
    }
}

bool check(ll timestart){
    lp(i, 1, n) lp(j, 1, n) d[i][j] = 0;
    d[st.first][st.second] = timestart;
    q.push(st);
    while(q.size()){
        ll u = q.front().first, v = q.front().second;
        q.pop();
        lp(i, 0, 3){
            ll nu = u + dx[i], nv = v + dy[i];
            if(a[nu][nv] == -1 || (d[nu][nv] != 0 && d[nu][nv] != d[u][v] + 1)) continue;
            d[nu][nv] = d[u][v] + 1;
            // if(u == 4 && v == 4) cerr << nu << ' ' << nv << ' ' << d[nu][nv] << '\n';
            if(a[nu][nv] > d[nu][nv]) q.push({nu, nv});
            bfs(nu, nv, 1, d[nu][nv]);
        }   
    }
    // lp(i, 1, n){
    //     lp(j, 1, n) cerr << d[i][j] << ' ';
    //     cerr << '\n';
    // }
    if(d[fi.first][fi.second] == 0 || !d[fi.first][fi.second]) 
        return 0;
    return 1;
}

int main(){
    giuncute();
    #ifndef ONLINE_JUDGE
    OF();
    #endif
    memset(a, -1, sizeof a);
    memset(d, -1, sizeof d);
    cin >> n >> s;
    lp(i, 1, n) lp(j, 1, n){
        char c;
        cin >> c;
        a[i][j] = 0;
        if(c == 'M') st = {i, j};
        else if(c == 'D') fi = {i, j};
        else if(c == 'T') a[i][j] = -1;
        else if(c == 'H') q.push({i, j}), a[i][j] = 1;
    }
    while(q.size()){
        ll u = q.front().first, v = q.front().second;
        q.pop();
        lp(i, 0, 3){
            ll nu = u + dx[i], nv = v + dy[i];
            if(a[nu][nv] || (nu == fi.first && nv == fi.second)) continue;
            a[nu][nv] = a[u][v] + 1;
            q.push({nu, nv});
        }
    }
    ll l = 1, r = n * n, ans = -1; 
    while(l <= r){
        ll mid = (l + r) >> 1;
        if(check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    if(ans != -1) ans -= 1;
    cout << ans;
}

Compilation message

mecho.cpp: In function 'void OF()':
mecho.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(Fname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(Fname".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10444 KB Output is correct
2 Correct 4 ms 10444 KB Output is correct
3 Correct 4 ms 10444 KB Output is correct
4 Correct 4 ms 10444 KB Output is correct
5 Incorrect 4 ms 10444 KB Output isn't correct
6 Incorrect 4 ms 10444 KB Output isn't correct
7 Runtime error 111 ms 65536 KB Execution killed with signal 9
8 Correct 4 ms 10444 KB Output is correct
9 Correct 67 ms 19168 KB Output is correct
10 Correct 4 ms 10444 KB Output is correct
11 Incorrect 4 ms 10444 KB Output isn't correct
12 Incorrect 4 ms 10444 KB Output isn't correct
13 Runtime error 149 ms 65536 KB Execution killed with signal 9
14 Runtime error 131 ms 65540 KB Execution killed with signal 9
15 Correct 4 ms 10444 KB Output is correct
16 Incorrect 5 ms 10540 KB Output isn't correct
17 Correct 4 ms 10444 KB Output is correct
18 Incorrect 11 ms 11060 KB Output isn't correct
19 Correct 4 ms 10444 KB Output is correct
20 Incorrect 48 ms 14448 KB Output isn't correct
21 Correct 4 ms 10444 KB Output is correct
22 Runtime error 232 ms 65540 KB Execution killed with signal 9
23 Correct 4 ms 10444 KB Output is correct
24 Runtime error 132 ms 65540 KB Execution killed with signal 9
25 Correct 4 ms 10444 KB Output is correct
26 Runtime error 132 ms 65540 KB Execution killed with signal 9
27 Correct 4 ms 10444 KB Output is correct
28 Runtime error 128 ms 65540 KB Execution killed with signal 9
29 Correct 4 ms 10416 KB Output is correct
30 Runtime error 132 ms 65540 KB Execution killed with signal 9
31 Correct 4 ms 10444 KB Output is correct
32 Runtime error 130 ms 65540 KB Execution killed with signal 9
33 Correct 12 ms 10444 KB Output is correct
34 Runtime error 137 ms 65540 KB Execution killed with signal 9
35 Runtime error 119 ms 65540 KB Execution killed with signal 9
36 Correct 13 ms 10444 KB Output is correct
37 Runtime error 128 ms 65540 KB Execution killed with signal 9
38 Runtime error 122 ms 65540 KB Execution killed with signal 9
39 Correct 15 ms 10444 KB Output is correct
40 Runtime error 133 ms 65540 KB Execution killed with signal 9
41 Runtime error 122 ms 65540 KB Execution killed with signal 9
42 Correct 18 ms 10528 KB Output is correct
43 Runtime error 138 ms 65540 KB Execution killed with signal 9
44 Runtime error 119 ms 65540 KB Execution killed with signal 9
45 Correct 20 ms 10468 KB Output is correct
46 Runtime error 133 ms 65540 KB Execution killed with signal 9
47 Runtime error 126 ms 65540 KB Execution killed with signal 9
48 Correct 26 ms 10440 KB Output is correct
49 Runtime error 132 ms 65540 KB Execution killed with signal 9
50 Runtime error 128 ms 65540 KB Execution killed with signal 9
51 Correct 27 ms 10464 KB Output is correct
52 Runtime error 133 ms 65540 KB Execution killed with signal 9
53 Runtime error 126 ms 65540 KB Execution killed with signal 9
54 Correct 31 ms 10444 KB Output is correct
55 Runtime error 134 ms 65540 KB Execution killed with signal 9
56 Runtime error 124 ms 65540 KB Execution killed with signal 9
57 Correct 37 ms 10468 KB Output is correct
58 Runtime error 140 ms 65540 KB Execution killed with signal 9
59 Runtime error 132 ms 65540 KB Execution killed with signal 9
60 Correct 39 ms 10444 KB Output is correct
61 Runtime error 139 ms 65540 KB Execution killed with signal 9
62 Runtime error 135 ms 65540 KB Execution killed with signal 9
63 Correct 212 ms 10488 KB Output is correct
64 Runtime error 146 ms 65540 KB Execution killed with signal 9
65 Incorrect 384 ms 10592 KB Output isn't correct
66 Correct 253 ms 10460 KB Output is correct
67 Correct 240 ms 10444 KB Output is correct
68 Runtime error 146 ms 65540 KB Execution killed with signal 9
69 Runtime error 145 ms 65540 KB Execution killed with signal 9
70 Runtime error 180 ms 65540 KB Execution killed with signal 9
71 Execution timed out 1089 ms 17484 KB Time limit exceeded
72 Runtime error 140 ms 65540 KB Execution killed with signal 9
73 Runtime error 123 ms 65540 KB Execution killed with signal 9
74 Runtime error 108 ms 65540 KB Execution killed with signal 9
75 Runtime error 127 ms 65540 KB Execution killed with signal 9
76 Runtime error 117 ms 65540 KB Execution killed with signal 9
77 Runtime error 108 ms 65540 KB Execution killed with signal 9
78 Runtime error 475 ms 65540 KB Execution killed with signal 9
79 Runtime error 109 ms 65540 KB Execution killed with signal 9
80 Runtime error 467 ms 65540 KB Execution killed with signal 9
81 Runtime error 119 ms 65540 KB Execution killed with signal 9
82 Runtime error 107 ms 65540 KB Execution killed with signal 9
83 Runtime error 235 ms 65540 KB Execution killed with signal 9
84 Runtime error 108 ms 65540 KB Execution killed with signal 9
85 Runtime error 109 ms 65540 KB Execution killed with signal 9
86 Runtime error 112 ms 65540 KB Execution killed with signal 9
87 Runtime error 109 ms 65540 KB Execution killed with signal 9
88 Runtime error 109 ms 65536 KB Execution killed with signal 9
89 Runtime error 106 ms 65540 KB Execution killed with signal 9
90 Runtime error 109 ms 65540 KB Execution killed with signal 9
91 Runtime error 119 ms 65540 KB Execution killed with signal 9
92 Runtime error 106 ms 65540 KB Execution killed with signal 9