Submission #18981


Source Code Expand

Copy
#include <queue>
#include <cctype>
#include <cstdio>
#include <algorithm>

using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

const int MAXN = 512;
char buf[MAXN][MAXN];
int tag[MAXN][MAXN];
double init[MAXN][MAXN];
double maxd[MAXN][MAXN];

int main() {
    int r, c, ts;
    double rate, ans;
    int sx = -1, sy = -1, tx = -1, ty = -1;
    vector<pair<pair<int, int>, double> > cur, pre;

    scanf("%d%d", &r, &c);
    for (int i = 1; i <= r; ++i) {
        scanf("%s", buf[i] + 1);
        for (int j = 1; j <= c; ++j) {
            if (buf[i][j] == 's') {
                sx = i;
                sy = j;
            } else if (isdigit(buf[i][j])) {
                init[i][j] = buf[i][j] - '0';
            }
        }
    }

    ts = 0;
    rate = 1.0;
    ans = 0.0;
    maxd[sx][sy] = 10.0;
    cur.push_back({{sx, sy}, maxd[sx][sy]});
    while (!cur.empty()) {
        ++ts;
        rate *= 0.99;
        pre.swap(cur);
        cur.clear();
        for (int i = 0; i < (int)pre.size(); ++i) {
            sx = pre[i].first.first;
            sy = pre[i].first.second;
            double sz = pre[i].second;
            // printf("[%d,%d,%d] %lf\n", sx, sy, ts, sz);
            for (int j = 0; j < 4; ++j) {
                tx = sx + dx[j];
                ty = sy + dy[j];
                if (buf[tx][ty] == 'g') {
                    ans = max(ans, sz);
                } else if (init[tx][ty] > 0) {
                    double tz = min(init[tx][ty] * rate, sz);
                    if (maxd[tx][ty] < tz) {
                        maxd[tx][ty] = tz;
                        if (tag[tx][ty] != ts) {
                            tag[tx][ty] = ts;
                            cur.push_back({{tx, ty}, 0.0});
                        }
                    }
                }
            }
        }
        for (int i = 0; i < (int)cur.size(); ++i) {
            cur[i].second = maxd[cur[i].first.first][cur[i].first.second];
        }
    }
    if (ans == 0.0) {
        puts("-1");
    } else {
        printf("%.10lf\n", ans);
    }

    return 0;
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User watashi
Language C++11 (GCC 4.8.1)
Score 100
Code Size 2182 Byte
Status AC
Exec Time 96 ms
Memory 6228 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:23:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:25:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name all
Score / Max Score 100 / 100
Status
AC × 64
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_mini_03.txt, 00_mini_04.txt, 00_mini_05.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_hard_01.txt, 03_hard_02.txt, 03_hard_03.txt, 03_hard_04.txt, 03_hard_05.txt, 03_hard_06.txt, 03_hard_07.txt, 03_hard_08.txt, 04_open_01.txt, 04_open_02.txt, 05_minihard_01.txt, 05_minihard_02.txt, 05_minihard_03.txt, 05_minihard_04.txt, 05_minihard_05.txt, 05_minihard_06.txt, 05_minihard_07.txt, 05_minihard_08.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 23 ms 784 KB
00_mini_02.txt AC 24 ms 856 KB
00_mini_03.txt AC 22 ms 784 KB
00_mini_04.txt AC 24 ms 776 KB
00_mini_05.txt AC 26 ms 852 KB
00_sample_01.txt AC 22 ms 780 KB
00_sample_02.txt AC 23 ms 784 KB
01_rnd_01.txt AC 64 ms 5216 KB
01_rnd_02.txt AC 46 ms 4560 KB
01_rnd_03.txt AC 30 ms 1544 KB
01_rnd_04.txt AC 35 ms 2688 KB
01_rnd_05.txt AC 26 ms 1424 KB
01_rnd_06.txt AC 23 ms 1164 KB
01_rnd_07.txt AC 41 ms 5196 KB
01_rnd_08.txt AC 62 ms 5736 KB
01_rnd_09.txt AC 80 ms 5124 KB
01_rnd_10.txt AC 71 ms 5508 KB
01_rnd_11.txt AC 53 ms 3432 KB
01_rnd_12.txt AC 42 ms 3052 KB
01_rnd_13.txt AC 27 ms 1148 KB
01_rnd_14.txt AC 53 ms 4224 KB
01_rnd_15.txt AC 39 ms 2960 KB
01_rnd_16.txt AC 32 ms 2308 KB
01_rnd_17.txt AC 34 ms 3592 KB
01_rnd_18.txt AC 24 ms 1040 KB
01_rnd_19.txt AC 26 ms 2316 KB
01_rnd_20.txt AC 26 ms 2692 KB
02_maxrnd_01.txt AC 69 ms 6144 KB
02_maxrnd_02.txt AC 74 ms 6220 KB
02_maxrnd_03.txt AC 80 ms 6144 KB
02_maxrnd_04.txt AC 86 ms 6216 KB
02_maxrnd_05.txt AC 84 ms 6140 KB
02_maxrnd_06.txt AC 86 ms 6140 KB
02_maxrnd_07.txt AC 88 ms 6152 KB
02_maxrnd_08.txt AC 93 ms 6228 KB
02_maxrnd_09.txt AC 95 ms 6224 KB
02_maxrnd_10.txt AC 96 ms 6140 KB
02_maxrnd_11.txt AC 95 ms 6144 KB
02_maxrnd_12.txt AC 92 ms 6212 KB
02_maxrnd_13.txt AC 85 ms 6152 KB
02_maxrnd_14.txt AC 79 ms 6208 KB
02_maxrnd_15.txt AC 65 ms 6016 KB
02_maxrnd_16.txt AC 57 ms 6020 KB
02_maxrnd_17.txt AC 50 ms 6020 KB
02_maxrnd_18.txt AC 30 ms 3596 KB
02_maxrnd_19.txt AC 28 ms 3460 KB
03_hard_01.txt AC 46 ms 6024 KB
03_hard_02.txt AC 48 ms 6124 KB
03_hard_03.txt AC 67 ms 6132 KB
03_hard_04.txt AC 68 ms 6024 KB
03_hard_05.txt AC 47 ms 6024 KB
03_hard_06.txt AC 46 ms 6016 KB
03_hard_07.txt AC 67 ms 6108 KB
03_hard_08.txt AC 65 ms 6096 KB
04_open_01.txt AC 48 ms 6100 KB
04_open_02.txt AC 66 ms 6116 KB
05_minihard_01.txt AC 24 ms 1040 KB
05_minihard_02.txt AC 23 ms 1116 KB
05_minihard_03.txt AC 23 ms 1036 KB
05_minihard_04.txt AC 27 ms 1100 KB
05_minihard_05.txt AC 23 ms 1036 KB
05_minihard_06.txt AC 25 ms 1040 KB
05_minihard_07.txt AC 25 ms 1036 KB
05_minihard_08.txt AC 23 ms 1032 KB