oj.uz

Submission #500201

# Submission time Handle Problem Language Result Execution time Memory
500201 2021-12-30T13:04:57 Z Nartifact Mecho (IOI09_mecho) C++17
5 / 100
 190 ms 7776 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 pii pair <int,int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()

const int N = 802, inf = 1e14;
const int H[] = {1, 0, -1, 0};
const int C[] = {0, 1, 0, -1};
int n, s;
char a[N][N];
int t[N][N];
bool cx[N][N];
pii sta, fin;

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

struct adt {int x, y, st;};

bool ok (const int& tg)
{
    queue <adt> q;
    memset(cx, 0, sizeof cx);
    q.push({sta.fi, sta.se, 0});
    cx[sta.fi][sta.se] = 1;
    while(q.size()) {
        auto tmp = q.front(); q.pop();
        if(tmp.x == fin.fi && tmp.y == fin.se) return 1;
        forinc(i,0,3) {
            int nh = tmp.x + H[i];
            int nc = tmp.y + C[i];
            if(valid(nh, nc) && !cx[nh][nc] && (tmp.st + 1) / s < t[nh][nc] - tg) {
                q.push({nh, nc, tmp.st + 1});
                cx[nh][nc] = 1;
            }
        }
    }
    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};
        else if(a[i][j] == 'D') fin = {i, j};
    }

    // bfs bee
    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) && nh != fin.fi && nc != fin.se
               && t[nh][nc] > t[x.fi][x.se] + 1) {
                t[nh][nc] = t[x.fi][x.se] + 1;
                q.push({nh, nc});
            }
        }
    }

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

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:98:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   98 | main ()
      | ^~~~
mecho.cpp: In function 'int main()':
mecho.cpp:103:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   freopen (task ".inp", "r", stdin);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:104:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   freopen (task ".out", "w", stdout);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 972 KB Output isn't correct
2 Incorrect 1 ms 972 KB Output isn't correct
3 Incorrect 1 ms 972 KB Output isn't correct
4 Incorrect 1 ms 964 KB Output isn't correct
5 Correct 1 ms 972 KB Output is correct
6 Incorrect 1 ms 972 KB Output isn't correct
7 Incorrect 163 ms 7572 KB Output isn't correct
8 Incorrect 1 ms 972 KB Output isn't correct
9 Incorrect 1 ms 972 KB Output isn't correct
10 Incorrect 1 ms 972 KB Output isn't correct
11 Incorrect 1 ms 972 KB Output isn't correct
12 Incorrect 1 ms 1228 KB Output isn't correct
13 Incorrect 1 ms 1228 KB Output isn't correct
14 Incorrect 1 ms 1228 KB Output isn't correct
15 Incorrect 1 ms 972 KB Output isn't correct
16 Incorrect 1 ms 964 KB Output isn't correct
17 Incorrect 1 ms 964 KB Output isn't correct
18 Incorrect 1 ms 972 KB Output isn't correct
19 Incorrect 1 ms 1100 KB Output isn't correct
20 Incorrect 1 ms 1100 KB Output isn't correct
21 Incorrect 2 ms 1100 KB Output isn't correct
22 Incorrect 1 ms 1092 KB Output isn't correct
23 Incorrect 1 ms 1228 KB Output isn't correct
24 Incorrect 1 ms 1228 KB Output isn't correct
25 Incorrect 1 ms 1228 KB Output isn't correct
26 Incorrect 1 ms 1228 KB Output isn't correct
27 Incorrect 1 ms 1228 KB Output isn't correct
28 Incorrect 1 ms 1228 KB Output isn't correct
29 Incorrect 1 ms 1228 KB Output isn't correct
30 Incorrect 1 ms 1360 KB Output isn't correct
31 Incorrect 1 ms 1356 KB Output isn't correct
32 Incorrect 1 ms 1356 KB Output isn't correct
33 Incorrect 4 ms 3540 KB Output isn't correct
34 Incorrect 4 ms 3508 KB Output isn't correct
35 Incorrect 10 ms 3540 KB Output isn't correct
36 Incorrect 5 ms 3908 KB Output isn't correct
37 Incorrect 6 ms 3896 KB Output isn't correct
38 Incorrect 11 ms 3916 KB Output isn't correct
39 Incorrect 5 ms 4288 KB Output isn't correct
40 Incorrect 7 ms 4292 KB Output isn't correct
41 Incorrect 11 ms 4300 KB Output isn't correct
42 Incorrect 5 ms 4684 KB Output isn't correct
43 Incorrect 7 ms 4684 KB Output isn't correct
44 Incorrect 17 ms 4752 KB Output isn't correct
45 Incorrect 7 ms 5188 KB Output isn't correct
46 Incorrect 11 ms 5064 KB Output isn't correct
47 Incorrect 28 ms 5132 KB Output isn't correct
48 Incorrect 9 ms 5464 KB Output isn't correct
49 Incorrect 10 ms 5572 KB Output isn't correct
50 Incorrect 31 ms 5492 KB Output isn't correct
51 Incorrect 8 ms 5836 KB Output isn't correct
52 Incorrect 12 ms 5964 KB Output isn't correct
53 Incorrect 40 ms 5972 KB Output isn't correct
54 Incorrect 10 ms 6340 KB Output isn't correct
55 Incorrect 13 ms 6340 KB Output isn't correct
56 Incorrect 49 ms 6368 KB Output isn't correct
57 Incorrect 10 ms 6708 KB Output isn't correct
58 Incorrect 14 ms 6732 KB Output isn't correct
59 Incorrect 52 ms 6804 KB Output isn't correct
60 Incorrect 12 ms 7108 KB Output isn't correct
61 Incorrect 20 ms 7164 KB Output isn't correct
62 Incorrect 46 ms 7188 KB Output isn't correct
63 Correct 122 ms 7232 KB Output is correct
64 Correct 190 ms 7236 KB Output is correct
65 Correct 156 ms 7232 KB Output is correct
66 Correct 112 ms 7228 KB Output is correct
67 Correct 115 ms 7224 KB Output is correct
68 Correct 50 ms 7180 KB Output is correct
69 Correct 51 ms 7168 KB Output is correct
70 Correct 43 ms 7288 KB Output is correct
71 Correct 55 ms 7164 KB Output is correct
72 Incorrect 32 ms 7244 KB Output isn't correct
73 Incorrect 41 ms 7756 KB Output isn't correct
74 Incorrect 95 ms 7704 KB Output isn't correct
75 Incorrect 102 ms 7776 KB Output isn't correct
76 Incorrect 101 ms 7700 KB Output isn't correct
77 Incorrect 101 ms 7688 KB Output isn't correct
78 Incorrect 64 ms 7620 KB Output isn't correct
79 Incorrect 43 ms 7684 KB Output isn't correct
80 Incorrect 49 ms 7696 KB Output isn't correct
81 Incorrect 121 ms 7664 KB Output isn't correct
82 Incorrect 55 ms 7652 KB Output isn't correct
83 Incorrect 145 ms 7656 KB Output isn't correct
84 Incorrect 64 ms 7520 KB Output isn't correct
85 Incorrect 53 ms 7568 KB Output isn't correct
86 Incorrect 52 ms 7636 KB Output isn't correct
87 Incorrect 65 ms 7532 KB Output isn't correct
88 Incorrect 50 ms 7424 KB Output isn't correct
89 Incorrect 72 ms 7448 KB Output isn't correct
90 Incorrect 100 ms 7424 KB Output isn't correct
91 Incorrect 50 ms 7544 KB Output isn't correct
92 Incorrect 55 ms 7620 KB Output isn't correct