oj.uz

답안 #571024

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
571024 2022-06-01T05:18:03 Z f4t4nt Mecho (IOI09_mecho) C++11
17 / 100
 293 ms 16272 KB 
#include <algorithm>
#include <cmath>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <tuple>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using ch = char;
using str = string;

#define pb push_back
#define elif else if
#define sz(C) (ll) C.size()
#define mp make_pair
#define mt make_tuple
#define flip(C) reverse(C.begin(), C.end())
#define ssort(C) sort(C.begin(), C.end())
#define rsort(C) sort(C.begin(), C.end(), greater<>())

#define FOR(x, e) for(ll  x = 0; x < (ll) e; x++)
#define FORR(x, e) for(ll x = (ll) e - 1; x >= 0; x--)
#define FOB(x, b, e) for(auto x = b; x < e; x++)
#define FOI(x, e, i) for(ll x = 0; x < (ll) e; x += (ll) i)
#define FOBI(x, b, e, i) for(ll x = (ll) b; x < (ll) e; x += (ll) i)
#define FORE(x, C) for(auto &x : C)

#ifdef LOCAL
#include "tester.cpp"
#define main test_main
extern istringstream fin;
extern ostringstream fout;
string test_file_name = "tests";
#define cin fin
#define cout fout
#endif

vector<int> di { -1, 0, 1, 0};
vector<int> dj { 0, -1, 0, 1};

void fill_b(ll &n, vector<vector<char>> &g, queue<pair<ll, ll>> &bfs_b, vector<vector<ll>> &d_b) {
    while(sz(bfs_b)) {
        ll i0 = bfs_b.front().first, j0 = bfs_b.front().second;
        bfs_b.pop();
        FOR(k, 4) {
            ll i1 = i0 + di[k], j1 = j0 + dj[k];
            if(i1 < 0 || i1 >= n || j1 < 0 || j1 >= n) continue;
            if(g[i1][j1] == 'T' || g[i1][j1] == 'D') continue;
            if(d_b[i1][j1] != 1e18) continue;
            d_b[i1][j1] = d_b[i0][j0] + 1;
            bfs_b.push({i1, j1});
        }
    }
}

bool valid(ll &mid, ll &n, ll &s, vector<vector<ll>> &d_b, vector<vector<char>> &g, queue<pair<ll, ll>> bfs_m, vector<vector<ll>> d_m) {
    while(sz(bfs_m)) {
        ll i0 = bfs_m.front().first, j0 = bfs_m.front().second, d = d_m[i0][j0] + 1;
        bfs_m.pop();
        FOR(k, 4) {
            ll i1 = i0 + di[k], j1 = j0 + dj[k];
            if(i1 < 0 || i1 >= n || j1 < 0 || j1 >= n) continue;
            if(g[i1][j1] == 'T') continue;
            if(d_m[i1][j1] != 1e18) continue;
            if(d_b[i1][j1] * s < mid * s + d) continue;
            if(g[i1][j1] == 'D') return true;
            d_m[i1][j1] = d;
            bfs_m.push({i1, j1});
        }
    }
    return false;
}

int main() {
    ll n, s, lo = 0;
    cin >> n >> s;
    ll hi = n * n;
    vector<vector<char>> g(n, vector<char>(n));
    vector<vector<ll>> d_b(n, vector<ll>(n, 1e18)), d_m(n, vector<ll>(n, 1e18));
    queue<pair<ll, ll>> bfs_b, bfs_m;
    FOR(i, n) FOR(j, n) {
        cin >> g[i][j];
        if(g[i][j] == 'H') {
            bfs_b.push({i, j});
            d_b[i][j] = 0;
        }
        elif(g[i][j] == 'M') {
            bfs_m.push({i, j});
            d_m[i][j] = 0;
        }
    }
    fill_b(n, g, bfs_b, d_b);
    if(!valid(lo, n, s, d_b, g, bfs_m, d_m)) {
        cout << "-1\n";
        return 0;
    }
    while(hi - lo > 0) {
        ll mid = lo + (hi - lo + 1) / 2;
        if(valid(mid, n, s, d_b, g, bfs_m, d_m)) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << '\n';
    return 0;
}

Subtask #1
17.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 224 ms 16260 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 1 ms 340 KB Output isn't correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Incorrect 1 ms 212 KB Output isn't correct
17 Incorrect 1 ms 212 KB Output isn't correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Incorrect 1 ms 212 KB Output isn't correct
20 Incorrect 1 ms 212 KB Output isn't correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Correct 1 ms 340 KB Output is correct
23 Incorrect 1 ms 340 KB Output isn't correct
24 Correct 1 ms 340 KB Output is correct
25 Incorrect 1 ms 340 KB Output isn't correct
26 Incorrect 1 ms 340 KB Output isn't correct
27 Incorrect 1 ms 340 KB Output isn't correct
28 Incorrect 1 ms 340 KB Output isn't correct
29 Incorrect 2 ms 340 KB Output isn't correct
30 Incorrect 1 ms 340 KB Output isn't correct
31 Incorrect 1 ms 340 KB Output isn't correct
32 Correct 1 ms 340 KB Output is correct
33 Incorrect 19 ms 3364 KB Output isn't correct
34 Incorrect 13 ms 3284 KB Output isn't correct
35 Incorrect 15 ms 3284 KB Output isn't correct
36 Incorrect 23 ms 4300 KB Output isn't correct
37 Incorrect 15 ms 4180 KB Output isn't correct
38 Incorrect 17 ms 4160 KB Output isn't correct
39 Incorrect 27 ms 5252 KB Output isn't correct
40 Correct 26 ms 5332 KB Output is correct
41 Correct 80 ms 5380 KB Output is correct
42 Incorrect 34 ms 6456 KB Output isn't correct
43 Incorrect 30 ms 6348 KB Output isn't correct
44 Correct 117 ms 6504 KB Output is correct
45 Incorrect 46 ms 7840 KB Output isn't correct
46 Incorrect 28 ms 7640 KB Output isn't correct
47 Incorrect 40 ms 7696 KB Output isn't correct
48 Incorrect 61 ms 9228 KB Output isn't correct
49 Correct 61 ms 9220 KB Output is correct
50 Incorrect 44 ms 9300 KB Output isn't correct
51 Incorrect 75 ms 10748 KB Output isn't correct
52 Incorrect 45 ms 10728 KB Output isn't correct
53 Correct 183 ms 10748 KB Output is correct
54 Incorrect 78 ms 12484 KB Output isn't correct
55 Correct 74 ms 12428 KB Output is correct
56 Incorrect 75 ms 12368 KB Output isn't correct
57 Incorrect 94 ms 14216 KB Output isn't correct
58 Correct 83 ms 14220 KB Output is correct
59 Incorrect 80 ms 14080 KB Output isn't correct
60 Incorrect 102 ms 16204 KB Output isn't correct
61 Incorrect 64 ms 16024 KB Output isn't correct
62 Correct 277 ms 16116 KB Output is correct
63 Correct 283 ms 16192 KB Output is correct
64 Incorrect 96 ms 16012 KB Output isn't correct
65 Correct 293 ms 16184 KB Output is correct
66 Incorrect 237 ms 16024 KB Output isn't correct
67 Correct 86 ms 16028 KB Output is correct
68 Correct 148 ms 16160 KB Output is correct
69 Incorrect 80 ms 16044 KB Output isn't correct
70 Correct 141 ms 16244 KB Output is correct
71 Incorrect 84 ms 16080 KB Output isn't correct
72 Incorrect 80 ms 16044 KB Output isn't correct
73 Incorrect 127 ms 16224 KB Output isn't correct
74 Correct 160 ms 16164 KB Output is correct
75 Incorrect 80 ms 16052 KB Output isn't correct
76 Correct 214 ms 16272 KB Output is correct
77 Correct 198 ms 16236 KB Output is correct
78 Correct 76 ms 15996 KB Output is correct
79 Incorrect 94 ms 16104 KB Output isn't correct
80 Incorrect 90 ms 16132 KB Output isn't correct
81 Correct 187 ms 16156 KB Output is correct
82 Correct 148 ms 16188 KB Output is correct
83 Incorrect 94 ms 16000 KB Output isn't correct
84 Correct 243 ms 16224 KB Output is correct
85 Correct 198 ms 16232 KB Output is correct
86 Incorrect 76 ms 16016 KB Output isn't correct
87 Correct 207 ms 16164 KB Output is correct
88 Correct 218 ms 16164 KB Output is correct
89 Incorrect 133 ms 16084 KB Output isn't correct
90 Correct 265 ms 16176 KB Output is correct
91 Incorrect 86 ms 16108 KB Output isn't correct
92 Incorrect 94 ms 16024 KB Output isn't correct