oj.uz

답안 #482486

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
482486 2021-10-24T21:38:45 Z danielsuh Mecho (IOI09_mecho) C++17
36 / 100
 1000 ms 65540 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

const int mxN = 805;
int N, S; 
char grid[mxN][mxN], store_grid[mxN][mxN];
int dist[mxN][mxN];
bool visited[mxN][mxN];
pair<int, int> start, finish;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

bool check(int seconds) {
    // Can you just simulate the first w seconds and then find the BFS thing?
    //O(N^2)
    memset(visited, 0, sizeof visited);
    for(int i = 0; i < N; i++) 
        for(int j = 0; j < N; j++)
            grid[i][j] = store_grid[i][j];
    
    //O(N^2)
    queue<pair<pair<int, int>, int>> bees;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(grid[i][j] == 'H') {
                bees.push({make_pair(i, j), 0});
            }
        }
    }

    //O(< N^2)
    while(!bees.empty()) {
        int x = bees.front().first.first, y = bees.front().first.second;
        int cur = bees.front().second;
        bees.pop();
        if(cur > seconds) continue;
        grid[x][y] = 'H';
        for(int it = 0; it < 4; it++) {
            if(x + dx[it] >= 0 && x + dx[it] < N && y + dy[it] >= 0 && y + dy[it] < N && grid[x + dx[it]][y + dy[it]] == 'G' && !visited[x + dx[it]][y + dy[it]]) {
                bees.push({make_pair(x + dx[it], y + dy[it]), cur + 1});
                visited[x + dx[it]][y + dy[it]] = true;
            }
        }
    }
    
    queue<pair<pair<int, int>, int>> q;
    for(auto &x : dist) for(auto &y : x) y = INT_MAX;
    q.push({make_pair(start.first, start.second), 0});
    dist[start.first][start.second] = 0;
    unordered_map<int, bool> considered;
    while(!q.empty()) {
        if(q.front().second % S == 0 && q.front().second != 0 && !considered[q.front().second]) {
            vector<pair<int, int>> change;
            for(int j = 0; j < N; j++) {
                for(int k = 0; k < N; k++) {
                    if(grid[j][k] == 'H') {
                        for(int it = 0; it < 4; it++) {
                            if(j + dx[it] >= 0 && j + dx[it] < N && k + dy[it] >= 0 && k + dy[it] < N && grid[j + dx[it]][k + dy[it]] != 'D' && grid[j + dx[it]][k + dy[it]] != 'M' && grid[j + dx[it]][k + dy[it]] != 'T') change.push_back({j + dx[it], k + dy[it]});
                        }
                    }
                }
            }
            for(auto &x : change) grid[x.first][x.second] = 'H';
            considered[q.front().second] = true;
            continue;
        }
        int x = q.front().first.first, y = q.front().first.second;
        int cur_second = q.front().second;
        q.pop();
        if(grid[x][y] == 'H' || grid[x][y] == 'T') continue;
        if(grid[x][y] == 'D') return true;
        for(int i = 0; i < 4; i++) {
            if(x + dx[i] >= 0 && y + dy[i] >= 0 && x + dx[i] < N && y + dy[i] < N && dist[x][y] + 1 < dist[x + dx[i]][y + dy[i]]) {
                q.push({make_pair(x + dx[i], y + dy[i]), cur_second + 1});
                dist[x + dx[i]][y + dy[i]] = dist[x][y] + 1;
            }
        }
    }
    return false;
}

int bin_search() {
    int lo = 0, hi = N * N;
    while(lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if(check(mid)) {
            lo = mid;
        }else {
            hi = mid - 1;
        }
    }
    return lo;
}

void solve() {
    cin >> N >> S;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> grid[i][j];
            store_grid[i][j] = grid[i][j];
            if(grid[i][j] == 'M') {
                start.first = i, start.second = j;
            }else if(grid[i][j] == 'D') {
                finish.first = i, finish.second = j;
            }
       }
    }
    int ans = bin_search();
    if(ans == 0) {
        ans = -1;
    }
    cout << ans << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for(int i = 1; i <= T; ++i) {
        solve();
    }
}

Subtask #1
36.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5964 KB Output is correct
2 Correct 5 ms 6048 KB Output is correct
3 Correct 6 ms 5964 KB Output is correct
4 Correct 5 ms 6092 KB Output is correct
5 Incorrect 5 ms 5964 KB Output isn't correct
6 Correct 7 ms 5964 KB Output is correct
7 Runtime error 248 ms 65536 KB Execution killed with signal 9
8 Correct 5 ms 6092 KB Output is correct
9 Correct 5 ms 6092 KB Output is correct
10 Correct 5 ms 5964 KB Output is correct
11 Correct 5 ms 6092 KB Output is correct
12 Incorrect 8 ms 6220 KB Output isn't correct
13 Incorrect 8 ms 6316 KB Output isn't correct
14 Correct 17 ms 6656 KB Output is correct
15 Correct 6 ms 6080 KB Output is correct
16 Correct 5 ms 5964 KB Output is correct
17 Correct 6 ms 6092 KB Output is correct
18 Correct 5 ms 6092 KB Output is correct
19 Correct 7 ms 6092 KB Output is correct
20 Correct 6 ms 6092 KB Output is correct
21 Correct 9 ms 6156 KB Output is correct
22 Correct 7 ms 6092 KB Output is correct
23 Correct 15 ms 6220 KB Output is correct
24 Correct 6 ms 6116 KB Output is correct
25 Correct 16 ms 6220 KB Output is correct
26 Correct 8 ms 6220 KB Output is correct
27 Correct 37 ms 6344 KB Output is correct
28 Correct 8 ms 6220 KB Output is correct
29 Correct 36 ms 6368 KB Output is correct
30 Correct 10 ms 6356 KB Output is correct
31 Correct 46 ms 6380 KB Output is correct
32 Correct 9 ms 6376 KB Output is correct
33 Execution timed out 1095 ms 10768 KB Time limit exceeded
34 Correct 80 ms 10564 KB Output is correct
35 Correct 53 ms 8244 KB Output is correct
36 Execution timed out 1095 ms 13516 KB Time limit exceeded
37 Correct 125 ms 13260 KB Output is correct
38 Correct 69 ms 9828 KB Output is correct
39 Execution timed out 1089 ms 14244 KB Time limit exceeded
40 Correct 144 ms 14028 KB Output is correct
41 Correct 96 ms 10612 KB Output is correct
42 Execution timed out 1100 ms 14940 KB Time limit exceeded
43 Correct 178 ms 14884 KB Output is correct
44 Correct 120 ms 13688 KB Output is correct
45 Execution timed out 1091 ms 20036 KB Time limit exceeded
46 Correct 233 ms 19872 KB Output is correct
47 Correct 115 ms 8904 KB Output is correct
48 Execution timed out 1098 ms 21044 KB Time limit exceeded
49 Correct 266 ms 20832 KB Output is correct
50 Correct 183 ms 10456 KB Output is correct
51 Execution timed out 1101 ms 21960 KB Time limit exceeded
52 Correct 308 ms 22092 KB Output is correct
53 Correct 167 ms 11016 KB Output is correct
54 Execution timed out 1094 ms 23240 KB Time limit exceeded
55 Correct 359 ms 23160 KB Output is correct
56 Correct 200 ms 13928 KB Output is correct
57 Execution timed out 1099 ms 32636 KB Time limit exceeded
58 Correct 452 ms 32580 KB Output is correct
59 Correct 228 ms 14792 KB Output is correct
60 Execution timed out 1092 ms 33772 KB Time limit exceeded
61 Correct 505 ms 33716 KB Output is correct
62 Correct 267 ms 20012 KB Output is correct
63 Execution timed out 1093 ms 20512 KB Time limit exceeded
64 Correct 410 ms 11392 KB Output is correct
65 Execution timed out 1061 ms 35676 KB Time limit exceeded
66 Execution timed out 1097 ms 21596 KB Time limit exceeded
67 Execution timed out 1098 ms 35700 KB Time limit exceeded
68 Execution timed out 1054 ms 33668 KB Time limit exceeded
69 Correct 398 ms 14696 KB Output is correct
70 Execution timed out 1088 ms 33700 KB Time limit exceeded
71 Execution timed out 1095 ms 33644 KB Time limit exceeded
72 Incorrect 780 ms 35656 KB Output isn't correct
73 Runtime error 271 ms 65540 KB Execution killed with signal 9
74 Runtime error 302 ms 65540 KB Execution killed with signal 9
75 Runtime error 268 ms 65536 KB Execution killed with signal 9
76 Runtime error 256 ms 65536 KB Execution killed with signal 9
77 Runtime error 266 ms 65540 KB Execution killed with signal 9
78 Runtime error 255 ms 65540 KB Execution killed with signal 9
79 Runtime error 352 ms 65540 KB Execution killed with signal 9
80 Runtime error 257 ms 65540 KB Execution killed with signal 9
81 Runtime error 258 ms 65536 KB Execution killed with signal 9
82 Runtime error 267 ms 65540 KB Execution killed with signal 9
83 Runtime error 251 ms 65540 KB Execution killed with signal 9
84 Runtime error 429 ms 65540 KB Execution killed with signal 9
85 Runtime error 643 ms 65540 KB Execution killed with signal 9
86 Runtime error 257 ms 65540 KB Execution killed with signal 9
87 Runtime error 258 ms 65540 KB Execution killed with signal 9
88 Runtime error 258 ms 65536 KB Execution killed with signal 9
89 Runtime error 302 ms 65540 KB Execution killed with signal 9
90 Runtime error 249 ms 65540 KB Execution killed with signal 9
91 Runtime error 254 ms 65540 KB Execution killed with signal 9
92 Runtime error 249 ms 65540 KB Execution killed with signal 9