답안 #1071972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071972	2024-08-23T12:54:44 Z	7again	Mecho (IOI09_mecho)	C++17	11 / 100	370 ms	12152 KB

mecho

#include <bits/stdc++.h>

using namespace std ;

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


int n , s ;
pair <int , int> Honey , Home ;
char a[N][N] ;

bool inside(int x , int y) {
    return (x >= 0 && y >= 0 && x < n && y < n && a[x][y] != 'T') ;
}
bool val(int x , int y) {
    return  x / s < y ;
}
bool ok(int time) {

    vector<vector<int>> mn2(N , vector<int>(N , 1e9)) ;
    queue<pair <int , int>>  q2 ;
    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < n ; j++) {
            if(a[i][j] == 'H') {
                q2.push({i, j}) ;
                mn2[i][j] = 0 ;
            }
        }
    }
    while(q2.size()) {
        pair <int , int> t = q2.front() ;
        q2.pop() ;
        for(int i = 0 ; i < 4 ; i++) {
            int x = t.first + dx[i] ;
            int y = t.second + dy[i] ;
            if(inside(x , y) &&  mn2[t.first][t.second] + 1 < mn2[x][y]) {
                mn2[x][y] = mn2[t.first][t.second] + 1 ;
                q2.push({x, y}) ;
            }
        }
    }

    vector<vector<int>> mn(N , vector<int>(N , 1e9)) ;
    queue <pair <int , int>> q ;
    mn[Honey.first][Honey.second] = 0 ;
    q.push(Honey) ;
    while(!q.empty()) {
        pair <int , int> t = q.front() ;
        q.pop() ;
        for(int i = 0 ; i < 4 ; i++) {
            int x = t.first + dx[i] ;
            int y = t.second + dy[i] ;
            if(val(mn[t.first][t.second] + 1 , mn2[x][y] - time) && inside(x , y) && mn[t.first][t.second] + 1 < mn[x][y]) {
                mn[x][y] = mn[t.first][t.second] + 1 ;
                q.push({x , y}) ;
            }
        }
    }
    if(mn[Home.first][Home.second] == 1e9)
        return  0 ;
    return  1 ;
}
int main() {
    cin >> n >> s ;

    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < n ; j++) {
            cin >> a[i][j] ;
            if(a[i][j] == 'M')
                Honey = {i , j} ;
            if(a[i][j] == 'D')
                Home = {i , j} ;
        }
    }

    int l = 0 , r = n * n + 1 ;
    while(l + 1 < r) {
        int m = (l + r) / 2 ;
        if(ok(m))
            l = m ;
        else
            r = m ;
    }
    cout << l << endl ;
}

Subtask #1

11.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	8 ms	10840 KB	Execution killed with signal 11
2	Runtime error	6 ms	10732 KB	Execution killed with signal 11
3	Runtime error	6 ms	10844 KB	Execution killed with signal 11
4	Runtime error	6 ms	10644 KB	Execution killed with signal 11
5	Correct	10 ms	5540 KB	Output is correct
6	Runtime error	6 ms	10844 KB	Execution killed with signal 11
7	Runtime error	39 ms	11908 KB	Execution killed with signal 11
8	Incorrect	11 ms	5524 KB	Output isn't correct
9	Correct	12 ms	5556 KB	Output is correct
10	Correct	14 ms	5524 KB	Output is correct
11	Correct	11 ms	5496 KB	Output is correct
12	Runtime error	6 ms	10840 KB	Execution killed with signal 11
13	Incorrect	10 ms	5536 KB	Output isn't correct
14	Incorrect	11 ms	5564 KB	Output isn't correct
15	Runtime error	6 ms	10840 KB	Execution killed with signal 11
16	Correct	12 ms	5624 KB	Output is correct
17	Runtime error	8 ms	10844 KB	Execution killed with signal 11
18	Correct	13 ms	5524 KB	Output is correct
19	Runtime error	6 ms	10844 KB	Execution killed with signal 11
20	Correct	14 ms	5628 KB	Output is correct
21	Runtime error	7 ms	10844 KB	Execution killed with signal 11
22	Correct	16 ms	5552 KB	Output is correct
23	Runtime error	6 ms	10844 KB	Execution killed with signal 11
24	Correct	17 ms	5644 KB	Output is correct
25	Runtime error	6 ms	10844 KB	Execution killed with signal 11
26	Correct	18 ms	5656 KB	Output is correct
27	Runtime error	6 ms	10844 KB	Execution killed with signal 11
28	Correct	19 ms	5648 KB	Output is correct
29	Runtime error	7 ms	10840 KB	Execution killed with signal 11
30	Correct	20 ms	5656 KB	Output is correct
31	Runtime error	6 ms	10844 KB	Execution killed with signal 11
32	Correct	20 ms	5656 KB	Output is correct
33	Runtime error	11 ms	11356 KB	Execution killed with signal 11
34	Correct	39 ms	5832 KB	Output is correct
35	Correct	56 ms	5832 KB	Output is correct
36	Runtime error	13 ms	11352 KB	Execution killed with signal 11
37	Correct	51 ms	5856 KB	Output is correct
38	Correct	72 ms	5820 KB	Output is correct
39	Runtime error	15 ms	11356 KB	Execution killed with signal 11
40	Correct	60 ms	5988 KB	Output is correct
41	Correct	93 ms	5876 KB	Output is correct
42	Runtime error	15 ms	11612 KB	Execution killed with signal 11
43	Correct	68 ms	5932 KB	Output is correct
44	Correct	103 ms	5884 KB	Output is correct
45	Runtime error	17 ms	11592 KB	Execution killed with signal 11
46	Correct	77 ms	5936 KB	Output is correct
47	Correct	130 ms	5948 KB	Output is correct
48	Runtime error	19 ms	11608 KB	Execution killed with signal 11
49	Correct	80 ms	5980 KB	Output is correct
50	Correct	184 ms	5984 KB	Output is correct
51	Runtime error	24 ms	11772 KB	Execution killed with signal 11
52	Correct	97 ms	6036 KB	Output is correct
53	Correct	187 ms	6032 KB	Output is correct
54	Runtime error	25 ms	11864 KB	Execution killed with signal 11
55	Correct	110 ms	6036 KB	Output is correct
56	Correct	197 ms	6076 KB	Output is correct
57	Runtime error	26 ms	11856 KB	Execution killed with signal 11
58	Correct	117 ms	6168 KB	Output is correct
59	Correct	229 ms	6088 KB	Output is correct
60	Runtime error	28 ms	11856 KB	Execution killed with signal 11
61	Runtime error	39 ms	11884 KB	Execution killed with signal 11
62	Runtime error	112 ms	11872 KB	Execution killed with signal 11
63	Runtime error	145 ms	11944 KB	Execution killed with signal 11
64	Runtime error	158 ms	11908 KB	Execution killed with signal 11
65	Runtime error	126 ms	12024 KB	Execution killed with signal 11
66	Runtime error	140 ms	12052 KB	Execution killed with signal 11
67	Runtime error	130 ms	11884 KB	Execution killed with signal 11
68	Runtime error	242 ms	12124 KB	Execution killed with signal 11
69	Runtime error	250 ms	11992 KB	Execution killed with signal 11
70	Runtime error	258 ms	12012 KB	Execution killed with signal 11
71	Runtime error	275 ms	12016 KB	Execution killed with signal 11
72	Runtime error	221 ms	11956 KB	Execution killed with signal 11
73	Runtime error	274 ms	12124 KB	Execution killed with signal 11
74	Runtime error	40 ms	12116 KB	Execution killed with signal 11
75	Runtime error	39 ms	12152 KB	Execution killed with signal 11
76	Runtime error	36 ms	12116 KB	Execution killed with signal 11
77	Runtime error	41 ms	12112 KB	Execution killed with signal 11
78	Incorrect	308 ms	6144 KB	Output isn't correct
79	Correct	278 ms	6156 KB	Output is correct
80	Correct	288 ms	6152 KB	Output is correct
81	Correct	297 ms	6148 KB	Output is correct
82	Correct	292 ms	6144 KB	Output is correct
83	Runtime error	165 ms	12032 KB	Execution killed with signal 11
84	Correct	328 ms	6060 KB	Output is correct
85	Correct	332 ms	6116 KB	Output is correct
86	Correct	332 ms	6136 KB	Output is correct
87	Correct	300 ms	6136 KB	Output is correct
88	Runtime error	162 ms	11936 KB	Execution killed with signal 11
89	Correct	323 ms	6152 KB	Output is correct
90	Correct	329 ms	6136 KB	Output is correct
91	Correct	370 ms	6140 KB	Output is correct
92	Correct	301 ms	6140 KB	Output is correct