oj.uz

Submission #484403

# Submission time Handle Problem Language Result Execution time Memory
484403 2021-11-03T09:00:08 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 "f"
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] >= a[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]) continue;
            a[nu][nv] = a[u][v] + 1;
            q.push({nu, nv});
        }
    }
    // lp(i, 1, n){
    //     lp(j, 1, n) cerr << a[i][j] << ' ';
    //     cerr << '\n';
    // }
    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 5 ms 10444 KB Output is correct
2 Incorrect 6 ms 10444 KB Output isn't correct
3 Correct 4 ms 10468 KB Output is correct
4 Incorrect 4 ms 10468 KB Output isn't correct
5 Incorrect 4 ms 10468 KB Output isn't correct
6 Incorrect 4 ms 10444 KB Output isn't correct
7 Runtime error 113 ms 65540 KB Execution killed with signal 9
8 Correct 4 ms 10444 KB Output is correct
9 Correct 65 ms 19444 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 5 ms 10460 KB Output isn't correct
13 Runtime error 149 ms 65536 KB Execution killed with signal 9
14 Runtime error 128 ms 65540 KB Execution killed with signal 9
15 Correct 4 ms 10444 KB Output is correct
16 Correct 5 ms 10460 KB Output is correct
17 Correct 4 ms 10444 KB Output is correct
18 Correct 15 ms 11064 KB Output is correct
19 Correct 4 ms 10444 KB Output is correct
20 Correct 52 ms 14448 KB Output is 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 126 ms 65540 KB Execution killed with signal 9
25 Correct 5 ms 10468 KB Output is correct
26 Runtime error 152 ms 65540 KB Execution killed with signal 9
27 Correct 5 ms 10444 KB Output is correct
28 Runtime error 126 ms 65540 KB Execution killed with signal 9
29 Correct 4 ms 10444 KB Output is correct
30 Runtime error 128 ms 65540 KB Execution killed with signal 9
31 Correct 5 ms 10444 KB Output is correct
32 Runtime error 144 ms 65540 KB Execution killed with signal 9
33 Correct 12 ms 10572 KB Output is correct
34 Runtime error 136 ms 65540 KB Execution killed with signal 9
35 Runtime error 129 ms 65540 KB Execution killed with signal 9
36 Correct 14 ms 10604 KB Output is correct
37 Runtime error 150 ms 65540 KB Execution killed with signal 9
38 Runtime error 118 ms 65540 KB Execution killed with signal 9
39 Correct 15 ms 10604 KB Output is correct
40 Runtime error 134 ms 65540 KB Execution killed with signal 9
41 Runtime error 129 ms 65540 KB Execution killed with signal 9
42 Correct 20 ms 10604 KB Output is correct
43 Runtime error 129 ms 65540 KB Execution killed with signal 9
44 Runtime error 119 ms 65540 KB Execution killed with signal 9
45 Correct 20 ms 10760 KB Output is correct
46 Runtime error 140 ms 65540 KB Execution killed with signal 9
47 Runtime error 123 ms 65540 KB Execution killed with signal 9
48 Correct 23 ms 10700 KB Output is correct
49 Runtime error 133 ms 65540 KB Execution killed with signal 9
50 Runtime error 134 ms 65540 KB Execution killed with signal 9
51 Correct 27 ms 10880 KB Output is correct
52 Runtime error 131 ms 65540 KB Execution killed with signal 9
53 Runtime error 124 ms 65540 KB Execution killed with signal 9
54 Correct 30 ms 10864 KB Output is correct
55 Runtime error 139 ms 65540 KB Execution killed with signal 9
56 Runtime error 126 ms 65540 KB Execution killed with signal 9
57 Correct 40 ms 10956 KB Output is correct
58 Runtime error 147 ms 65540 KB Execution killed with signal 9
59 Runtime error 150 ms 65540 KB Execution killed with signal 9
60 Correct 38 ms 11072 KB Output is correct
61 Runtime error 134 ms 65540 KB Execution killed with signal 9
62 Runtime error 130 ms 65540 KB Execution killed with signal 9
63 Correct 231 ms 11096 KB Output is correct
64 Runtime error 151 ms 65540 KB Execution killed with signal 9
65 Incorrect 403 ms 11208 KB Output isn't correct
66 Correct 257 ms 11096 KB Output is correct
67 Correct 250 ms 11092 KB Output is correct
68 Runtime error 152 ms 65540 KB Execution killed with signal 9
69 Runtime error 144 ms 65540 KB Execution killed with signal 9
70 Runtime error 204 ms 65540 KB Execution killed with signal 9
71 Execution timed out 1094 ms 18208 KB Time limit exceeded
72 Runtime error 142 ms 65540 KB Execution killed with signal 9
73 Runtime error 147 ms 65540 KB Execution killed with signal 9
74 Runtime error 111 ms 65540 KB Execution killed with signal 9
75 Runtime error 135 ms 65540 KB Execution killed with signal 9
76 Runtime error 124 ms 65540 KB Execution killed with signal 9
77 Runtime error 111 ms 65540 KB Execution killed with signal 9
78 Runtime error 502 ms 65540 KB Execution killed with signal 9
79 Runtime error 110 ms 65540 KB Execution killed with signal 9
80 Runtime error 486 ms 65540 KB Execution killed with signal 9
81 Runtime error 128 ms 65540 KB Execution killed with signal 9
82 Runtime error 111 ms 65540 KB Execution killed with signal 9
83 Runtime error 242 ms 65540 KB Execution killed with signal 9
84 Runtime error 131 ms 65540 KB Execution killed with signal 9
85 Runtime error 109 ms 65540 KB Execution killed with signal 9
86 Runtime error 110 ms 65540 KB Execution killed with signal 9
87 Runtime error 110 ms 65536 KB Execution killed with signal 9
88 Runtime error 118 ms 65540 KB Execution killed with signal 9
89 Runtime error 110 ms 65540 KB Execution killed with signal 9
90 Runtime error 118 ms 65536 KB Execution killed with signal 9
91 Runtime error 116 ms 65540 KB Execution killed with signal 9
92 Runtime error 116 ms 65536 KB Execution killed with signal 9