답안 #535622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535622	2022-03-10T16:55:42 Z	louiskwok	Mecho (IOI09_mecho)	C++17	33 / 100	195 ms	9348 KB

mecho

#include <bits/stdc++.h>
using namespace std;
bool visited[805][805];
int distBee[805][805];
double distBear[805][805];
char g[805][805];
int dr[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};
int n,sr,sc,er,ec,mxtime;
double s;
bool possible(double t) {
    memset(visited,0,sizeof visited);
    queue < pair<int,int> > bfs;
    distBear[sr][sc] = t;
    bfs.push({sr,sc});
    while (!bfs.empty()) {
        int curR = bfs.front().first;
        int curC = bfs.front().second;
        bfs.pop();
        for (int i=0;i<4;i++) {
            int nr = curR + dr[i];
            int nc = curC + dc[i];
            if (nr<1||nr>n||nc<1||nc>n||visited[nr][nc]||g[nr][nc]=='T'||distBear[curR][curC]+(double)1/s>(double)distBee[nr][nc]) continue;
            if (nr==er&&nc==ec&&distBear[curR][curC]+(double)1/s<=(double)distBee[nr][nc]) return true;
            visited[nr][nc] = true;
            distBear[nr][nc] = distBear[curR][curC]+1/s;
            bfs.push({nr,nc});
        }
    }
    if (visited[er][ec]) return true;
    return false;
}
int main() {
    queue < pair<int,int> > bfs;
    cin >> n >> s;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) {
            cin >> g[i][j];
            if (g[i][j]=='M') sr = i,sc = j;
            else if (g[i][j]=='D') er = i,ec = j;
            else if (g[i][j]=='H') {
                visited[i][j] = true;
                bfs.push({i,j});
            }
        }
    }
    while (!bfs.empty()) {
        int curR = bfs.front().first;
        int curC = bfs.front().second;
        bfs.pop();
        for (int i=0;i<4;i++) {
            int nr = curR + dr[i];
            int nc = curC + dc[i];
            if (nr==sr&&nc==sc) distBee[nr][nc] = distBee[curR][curC]+1;
            if (nr<1||nr>n||nc<1||nc>n||visited[nr][nc]||g[nr][nc]=='T'||g[nr][nc]=='M') continue;
            visited[nr][nc] = true;
            distBee[nr][nc] = distBee[curR][curC]+1;
            mxtime = max(mxtime,distBee[nr][nc]);
            bfs.push({nr,nc});
        }
    }
    int lo = 0,hi = distBee[sr][sc]-1;
    while (lo<hi) {
        int mid = (lo+hi+1)/2;
        if (possible((double)mid)) lo = mid;
        else hi = mid-1;
    }
    if (!possible(0)) cout << -1 << endl;
    else cout << lo << endl;
    return 0;
}

Subtask #1

33.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	980 KB	Output isn't correct
2	Incorrect	1 ms	980 KB	Output isn't correct
3	Incorrect	1 ms	980 KB	Output isn't correct
4	Incorrect	1 ms	980 KB	Output isn't correct
5	Correct	1 ms	980 KB	Output is correct
6	Incorrect	1 ms	980 KB	Output isn't correct
7	Incorrect	115 ms	9108 KB	Output isn't correct
8	Incorrect	1 ms	980 KB	Output isn't correct
9	Correct	1 ms	980 KB	Output is correct
10	Correct	1 ms	980 KB	Output is correct
11	Correct	1 ms	980 KB	Output is correct
12	Incorrect	1 ms	1364 KB	Output isn't correct
13	Incorrect	1 ms	1236 KB	Output isn't correct
14	Correct	2 ms	1236 KB	Output is correct
15	Incorrect	1 ms	980 KB	Output isn't correct
16	Correct	1 ms	980 KB	Output is correct
17	Incorrect	1 ms	980 KB	Output isn't correct
18	Correct	1 ms	980 KB	Output is correct
19	Incorrect	1 ms	980 KB	Output isn't correct
20	Correct	1 ms	980 KB	Output is correct
21	Incorrect	1 ms	1108 KB	Output isn't correct
22	Correct	1 ms	1108 KB	Output is correct
23	Incorrect	1 ms	1108 KB	Output isn't correct
24	Correct	1 ms	1108 KB	Output is correct
25	Incorrect	1 ms	1108 KB	Output isn't correct
26	Correct	1 ms	1108 KB	Output is correct
27	Incorrect	1 ms	1108 KB	Output isn't correct
28	Correct	1 ms	1236 KB	Output is correct
29	Incorrect	1 ms	1108 KB	Output isn't correct
30	Correct	1 ms	1236 KB	Output is correct
31	Incorrect	1 ms	1236 KB	Output isn't correct
32	Correct	2 ms	1236 KB	Output is correct
33	Incorrect	11 ms	2240 KB	Output isn't correct
34	Correct	13 ms	2336 KB	Output is correct
35	Correct	32 ms	4520 KB	Output is correct
36	Incorrect	12 ms	2516 KB	Output isn't correct
37	Correct	12 ms	2516 KB	Output is correct
38	Correct	32 ms	5020 KB	Output is correct
39	Incorrect	14 ms	2668 KB	Output isn't correct
40	Correct	16 ms	2656 KB	Output is correct
41	Correct	45 ms	5440 KB	Output is correct
42	Incorrect	18 ms	2840 KB	Output isn't correct
43	Correct	23 ms	2952 KB	Output is correct
44	Correct	61 ms	6036 KB	Output is correct
45	Incorrect	22 ms	3100 KB	Output isn't correct
46	Correct	22 ms	3168 KB	Output is correct
47	Correct	65 ms	6484 KB	Output is correct
48	Incorrect	25 ms	3216 KB	Output isn't correct
49	Correct	24 ms	3320 KB	Output is correct
50	Correct	78 ms	6988 KB	Output is correct
51	Incorrect	34 ms	3452 KB	Output isn't correct
52	Correct	31 ms	3512 KB	Output is correct
53	Correct	106 ms	7464 KB	Output is correct
54	Incorrect	32 ms	3580 KB	Output isn't correct
55	Correct	35 ms	3696 KB	Output is correct
56	Correct	110 ms	8200 KB	Output is correct
57	Incorrect	40 ms	3776 KB	Output isn't correct
58	Correct	38 ms	3916 KB	Output is correct
59	Correct	123 ms	8476 KB	Output is correct
60	Incorrect	43 ms	4072 KB	Output isn't correct
61	Correct	43 ms	4124 KB	Output is correct
62	Correct	154 ms	9176 KB	Output is correct
63	Correct	125 ms	8956 KB	Output is correct
64	Correct	188 ms	9000 KB	Output is correct
65	Correct	195 ms	9060 KB	Output is correct
66	Correct	171 ms	9060 KB	Output is correct
67	Correct	139 ms	8860 KB	Output is correct
68	Correct	80 ms	8576 KB	Output is correct
69	Correct	67 ms	8840 KB	Output is correct
70	Correct	66 ms	8448 KB	Output is correct
71	Correct	68 ms	8380 KB	Output is correct
72	Incorrect	87 ms	8944 KB	Output isn't correct
73	Incorrect	92 ms	9340 KB	Output isn't correct
74	Correct	93 ms	9320 KB	Output is correct
75	Correct	91 ms	9348 KB	Output is correct
76	Correct	93 ms	9188 KB	Output is correct
77	Correct	93 ms	9236 KB	Output is correct
78	Correct	97 ms	6648 KB	Output is correct
79	Correct	88 ms	9296 KB	Output is correct
80	Correct	83 ms	6640 KB	Output is correct
81	Correct	100 ms	6676 KB	Output is correct
82	Correct	87 ms	6860 KB	Output is correct
83	Correct	101 ms	6732 KB	Output is correct
84	Correct	101 ms	9272 KB	Output is correct
85	Correct	98 ms	6748 KB	Output is correct
86	Correct	108 ms	6860 KB	Output is correct
87	Correct	101 ms	7108 KB	Output is correct
88	Correct	100 ms	6968 KB	Output is correct
89	Correct	109 ms	9176 KB	Output is correct
90	Correct	114 ms	8308 KB	Output is correct
91	Correct	124 ms	9264 KB	Output is correct
92	Correct	114 ms	7212 KB	Output is correct