답안 #1071970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071970	2024-08-23T12:53:16 Z	7again	Mecho (IOI09_mecho)	C++17	11 / 100	327 ms	12180 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 + 1 , vector<int>(n + 1 , 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 + 1 , vector<int>(n + 1 , 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	0 ms	344 KB	Execution killed with signal 11
2	Runtime error	0 ms	348 KB	Execution killed with signal 11
3	Runtime error	0 ms	348 KB	Execution killed with signal 11
4	Runtime error	0 ms	348 KB	Execution killed with signal 11
5	Correct	0 ms	348 KB	Output is correct
6	Runtime error	1 ms	348 KB	Execution killed with signal 11
7	Runtime error	36 ms	12120 KB	Execution killed with signal 11
8	Incorrect	0 ms	348 KB	Output isn't correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Runtime error	1 ms	604 KB	Execution killed with signal 11
13	Incorrect	1 ms	348 KB	Output isn't correct
14	Incorrect	1 ms	348 KB	Output isn't correct
15	Runtime error	0 ms	604 KB	Execution killed with signal 11
16	Correct	0 ms	348 KB	Output is correct
17	Runtime error	1 ms	604 KB	Execution killed with signal 11
18	Correct	0 ms	348 KB	Output is correct
19	Runtime error	1 ms	604 KB	Execution killed with signal 11
20	Correct	0 ms	348 KB	Output is correct
21	Runtime error	1 ms	604 KB	Execution killed with signal 11
22	Correct	0 ms	348 KB	Output is correct
23	Runtime error	1 ms	604 KB	Execution killed with signal 11
24	Correct	1 ms	348 KB	Output is correct
25	Runtime error	1 ms	604 KB	Execution killed with signal 11
26	Correct	1 ms	348 KB	Output is correct
27	Runtime error	1 ms	604 KB	Execution killed with signal 11
28	Correct	1 ms	348 KB	Output is correct
29	Runtime error	1 ms	604 KB	Execution killed with signal 11
30	Correct	1 ms	348 KB	Output is correct
31	Runtime error	1 ms	604 KB	Execution killed with signal 11
32	Correct	1 ms	348 KB	Output is correct
33	Runtime error	6 ms	2908 KB	Execution killed with signal 11
34	Correct	25 ms	1696 KB	Output is correct
35	Correct	45 ms	1700 KB	Output is correct
36	Runtime error	8 ms	3676 KB	Execution killed with signal 11
37	Correct	33 ms	2096 KB	Output is correct
38	Correct	59 ms	1880 KB	Output is correct
39	Runtime error	9 ms	4440 KB	Execution killed with signal 11
40	Correct	43 ms	2396 KB	Output is correct
41	Correct	80 ms	2408 KB	Output is correct
42	Runtime error	12 ms	5224 KB	Execution killed with signal 11
43	Correct	53 ms	2824 KB	Output is correct
44	Correct	96 ms	2800 KB	Output is correct
45	Runtime error	14 ms	6236 KB	Execution killed with signal 11
46	Correct	66 ms	3276 KB	Output is correct
47	Correct	112 ms	3272 KB	Output is correct
48	Runtime error	17 ms	7260 KB	Execution killed with signal 11
49	Correct	72 ms	3784 KB	Output is correct
50	Correct	144 ms	3780 KB	Output is correct
51	Runtime error	20 ms	8284 KB	Execution killed with signal 11
52	Correct	90 ms	4332 KB	Output is correct
53	Correct	171 ms	4300 KB	Output is correct
54	Runtime error	23 ms	9552 KB	Execution killed with signal 11
55	Correct	103 ms	4908 KB	Output is correct
56	Correct	198 ms	4856 KB	Output is correct
57	Runtime error	41 ms	10580 KB	Execution killed with signal 11
58	Correct	118 ms	5480 KB	Output is correct
59	Correct	222 ms	5492 KB	Output is correct
60	Runtime error	28 ms	11864 KB	Execution killed with signal 11
61	Correct	142 ms	6144 KB	Output is correct
62	Correct	258 ms	6128 KB	Output is correct
63	Runtime error	202 ms	12100 KB	Execution killed with signal 11
64	Runtime error	157 ms	12056 KB	Execution killed with signal 11
65	Runtime error	180 ms	12068 KB	Execution killed with signal 11
66	Runtime error	170 ms	12064 KB	Execution killed with signal 11
67	Runtime error	211 ms	12052 KB	Execution killed with signal 11
68	Runtime error	251 ms	12084 KB	Execution killed with signal 11
69	Runtime error	248 ms	11944 KB	Execution killed with signal 11
70	Runtime error	261 ms	12068 KB	Execution killed with signal 11
71	Correct	319 ms	6096 KB	Output is correct
72	Incorrect	309 ms	6136 KB	Output isn't correct
73	Incorrect	299 ms	6140 KB	Output isn't correct
74	Runtime error	36 ms	12112 KB	Execution killed with signal 11
75	Runtime error	40 ms	12112 KB	Execution killed with signal 11
76	Runtime error	39 ms	12112 KB	Execution killed with signal 11
77	Runtime error	43 ms	12112 KB	Execution killed with signal 11
78	Incorrect	313 ms	6132 KB	Output isn't correct
79	Correct	288 ms	6164 KB	Output is correct
80	Correct	284 ms	6144 KB	Output is correct
81	Correct	293 ms	6160 KB	Output is correct
82	Correct	301 ms	6120 KB	Output is correct
83	Runtime error	160 ms	12096 KB	Execution killed with signal 11
84	Correct	316 ms	6168 KB	Output is correct
85	Correct	325 ms	6148 KB	Output is correct
86	Correct	322 ms	6144 KB	Output is correct
87	Correct	320 ms	6168 KB	Output is correct
88	Runtime error	163 ms	12180 KB	Execution killed with signal 11
89	Correct	325 ms	6152 KB	Output is correct
90	Correct	327 ms	6148 KB	Output is correct
91	Correct	311 ms	6156 KB	Output is correct
92	Correct	303 ms	6104 KB	Output is correct