답안 #1072023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1072023	2024-08-23T13:27:18 Z	7again	Mecho (IOI09_mecho)	C++17	5 / 100	342 ms	12144 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 ;
    if(mn2[Honey.first][Honey.second] > time)
        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

5.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1 ms	348 KB	Execution killed with signal 11
2	Runtime error	0 ms	348 KB	Execution killed with signal 11
3	Runtime error	1 ms	348 KB	Execution killed with signal 11
4	Runtime error	1 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	181 ms	12068 KB	Execution killed with signal 11
8	Runtime error	1 ms	604 KB	Execution killed with signal 11
9	Runtime error	1 ms	348 KB	Execution killed with signal 11
10	Runtime error	1 ms	348 KB	Execution killed with signal 11
11	Runtime error	1 ms	348 KB	Execution killed with signal 11
12	Runtime error	1 ms	604 KB	Execution killed with signal 11
13	Correct	1 ms	348 KB	Output is correct
14	Incorrect	1 ms	348 KB	Output isn't correct
15	Runtime error	0 ms	348 KB	Execution killed with signal 11
16	Runtime error	1 ms	348 KB	Execution killed with signal 11
17	Runtime error	0 ms	604 KB	Execution killed with signal 11
18	Runtime error	0 ms	604 KB	Execution killed with signal 11
19	Runtime error	0 ms	604 KB	Execution killed with signal 11
20	Runtime error	1 ms	604 KB	Execution killed with signal 11
21	Runtime error	0 ms	604 KB	Execution killed with signal 11
22	Runtime error	1 ms	604 KB	Execution killed with signal 11
23	Runtime error	1 ms	604 KB	Execution killed with signal 11
24	Runtime error	1 ms	604 KB	Execution killed with signal 11
25	Runtime error	1 ms	604 KB	Execution killed with signal 11
26	Runtime error	1 ms	604 KB	Execution killed with signal 11
27	Runtime error	1 ms	604 KB	Execution killed with signal 11
28	Runtime error	1 ms	604 KB	Execution killed with signal 11
29	Runtime error	1 ms	604 KB	Execution killed with signal 11
30	Runtime error	1 ms	604 KB	Execution killed with signal 11
31	Runtime error	1 ms	604 KB	Execution killed with signal 11
32	Runtime error	1 ms	604 KB	Execution killed with signal 11
33	Runtime error	7 ms	3100 KB	Execution killed with signal 11
34	Runtime error	9 ms	2996 KB	Execution killed with signal 11
35	Runtime error	21 ms	3012 KB	Execution killed with signal 11
36	Runtime error	9 ms	3800 KB	Execution killed with signal 11
37	Runtime error	10 ms	3552 KB	Execution killed with signal 11
38	Runtime error	30 ms	3704 KB	Execution killed with signal 11
39	Runtime error	13 ms	4496 KB	Execution killed with signal 11
40	Runtime error	14 ms	4548 KB	Execution killed with signal 11
41	Runtime error	39 ms	4520 KB	Execution killed with signal 11
42	Runtime error	15 ms	5388 KB	Execution killed with signal 11
43	Runtime error	17 ms	5312 KB	Execution killed with signal 11
44	Runtime error	42 ms	5164 KB	Execution killed with signal 11
45	Runtime error	17 ms	6268 KB	Execution killed with signal 11
46	Runtime error	18 ms	6080 KB	Execution killed with signal 11
47	Runtime error	71 ms	6232 KB	Execution killed with signal 11
48	Runtime error	20 ms	7080 KB	Execution killed with signal 11
49	Runtime error	25 ms	7156 KB	Execution killed with signal 11
50	Runtime error	88 ms	7224 KB	Execution killed with signal 11
51	Runtime error	23 ms	8256 KB	Execution killed with signal 11
52	Runtime error	27 ms	8204 KB	Execution killed with signal 11
53	Runtime error	87 ms	8372 KB	Execution killed with signal 11
54	Runtime error	28 ms	9376 KB	Execution killed with signal 11
55	Runtime error	30 ms	9412 KB	Execution killed with signal 11
56	Runtime error	92 ms	9456 KB	Execution killed with signal 11
57	Runtime error	31 ms	10616 KB	Execution killed with signal 11
58	Runtime error	36 ms	10644 KB	Execution killed with signal 11
59	Runtime error	116 ms	10784 KB	Execution killed with signal 11
60	Runtime error	34 ms	12044 KB	Execution killed with signal 11
61	Runtime error	39 ms	12048 KB	Execution killed with signal 11
62	Runtime error	120 ms	11900 KB	Execution killed with signal 11
63	Runtime error	138 ms	11952 KB	Execution killed with signal 11
64	Runtime error	186 ms	11872 KB	Execution killed with signal 11
65	Runtime error	124 ms	11880 KB	Execution killed with signal 11
66	Runtime error	140 ms	12056 KB	Execution killed with signal 11
67	Runtime error	130 ms	11904 KB	Execution killed with signal 11
68	Runtime error	242 ms	12144 KB	Execution killed with signal 11
69	Runtime error	252 ms	12096 KB	Execution killed with signal 11
70	Runtime error	258 ms	12096 KB	Execution killed with signal 11
71	Runtime error	275 ms	12052 KB	Execution killed with signal 11
72	Runtime error	252 ms	12112 KB	Execution killed with signal 11
73	Runtime error	315 ms	11940 KB	Execution killed with signal 11
74	Runtime error	207 ms	12088 KB	Execution killed with signal 11
75	Runtime error	174 ms	12136 KB	Execution killed with signal 11
76	Runtime error	172 ms	12108 KB	Execution killed with signal 11
77	Runtime error	179 ms	12064 KB	Execution killed with signal 11
78	Incorrect	297 ms	6148 KB	Output isn't correct
79	Correct	282 ms	6124 KB	Output is correct
80	Correct	287 ms	6392 KB	Output is correct
81	Correct	290 ms	6156 KB	Output is correct
82	Correct	298 ms	6116 KB	Output is correct
83	Runtime error	166 ms	12032 KB	Execution killed with signal 11
84	Correct	319 ms	6056 KB	Output is correct
85	Correct	342 ms	6120 KB	Output is correct
86	Correct	320 ms	6160 KB	Output is correct
87	Correct	308 ms	6160 KB	Output is correct
88	Runtime error	165 ms	11928 KB	Execution killed with signal 11
89	Correct	327 ms	6128 KB	Output is correct
90	Correct	324 ms	6136 KB	Output is correct
91	Correct	308 ms	6152 KB	Output is correct
92	Correct	327 ms	6020 KB	Output is correct