답안 #1072020

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1072020	2024-08-23T13:25:43 Z	7again	Mecho (IOI09_mecho)	C++17	14 / 100	368 ms	12184 KB

mecho

#include <bits/stdc++.h>

using namespace std ;

const int N = 801 ;
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

14.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	8 ms	10676 KB	Execution killed with signal 11
2	Runtime error	7 ms	10760 KB	Execution killed with signal 11
3	Runtime error	8 ms	10872 KB	Execution killed with signal 11
4	Runtime error	8 ms	10680 KB	Execution killed with signal 11
5	Correct	8 ms	5532 KB	Output is correct
6	Runtime error	11 ms	10856 KB	Execution killed with signal 11
7	Runtime error	188 ms	11980 KB	Execution killed with signal 11
8	Incorrect	11 ms	5496 KB	Output isn't correct
9	Correct	13 ms	5620 KB	Output is correct
10	Correct	12 ms	5572 KB	Output is correct
11	Correct	11 ms	5496 KB	Output is correct
12	Runtime error	19 ms	11020 KB	Execution killed with signal 11
13	Correct	11 ms	5564 KB	Output is correct
14	Incorrect	10 ms	5560 KB	Output isn't correct
15	Runtime error	7 ms	10760 KB	Execution killed with signal 11
16	Correct	12 ms	5592 KB	Output is correct
17	Runtime error	7 ms	10760 KB	Execution killed with signal 11
18	Correct	14 ms	5592 KB	Output is correct
19	Runtime error	8 ms	10756 KB	Execution killed with signal 11
20	Correct	15 ms	5556 KB	Output is correct
21	Runtime error	7 ms	10936 KB	Execution killed with signal 11
22	Correct	21 ms	5796 KB	Output is correct
23	Runtime error	7 ms	10760 KB	Execution killed with signal 11
24	Correct	16 ms	5592 KB	Output is correct
25	Runtime error	7 ms	10760 KB	Execution killed with signal 11
26	Correct	17 ms	5604 KB	Output is correct
27	Runtime error	7 ms	10760 KB	Execution killed with signal 11
28	Correct	18 ms	5688 KB	Output is correct
29	Runtime error	7 ms	10760 KB	Execution killed with signal 11
30	Correct	20 ms	5692 KB	Output is correct
31	Runtime error	7 ms	11012 KB	Execution killed with signal 11
32	Correct	20 ms	5604 KB	Output is correct
33	Runtime error	14 ms	11272 KB	Execution killed with signal 11
34	Correct	40 ms	5848 KB	Output is correct
35	Correct	61 ms	5880 KB	Output is correct
36	Runtime error	14 ms	11272 KB	Execution killed with signal 11
37	Correct	51 ms	5856 KB	Output is correct
38	Correct	66 ms	5852 KB	Output is correct
39	Runtime error	16 ms	11524 KB	Execution killed with signal 11
40	Correct	57 ms	5896 KB	Output is correct
41	Correct	95 ms	5884 KB	Output is correct
42	Runtime error	19 ms	11528 KB	Execution killed with signal 11
43	Correct	65 ms	5964 KB	Output is correct
44	Correct	101 ms	5908 KB	Output is correct
45	Runtime error	20 ms	11516 KB	Execution killed with signal 11
46	Correct	79 ms	5956 KB	Output is correct
47	Correct	122 ms	5944 KB	Output is correct
48	Runtime error	22 ms	11784 KB	Execution killed with signal 11
49	Correct	85 ms	5984 KB	Output is correct
50	Correct	153 ms	6024 KB	Output is correct
51	Runtime error	25 ms	11680 KB	Execution killed with signal 11
52	Correct	96 ms	6036 KB	Output is correct
53	Correct	199 ms	6024 KB	Output is correct
54	Runtime error	28 ms	11732 KB	Execution killed with signal 11
55	Correct	111 ms	6124 KB	Output is correct
56	Correct	195 ms	6060 KB	Output is correct
57	Runtime error	35 ms	11900 KB	Execution killed with signal 11
58	Correct	131 ms	6068 KB	Output is correct
59	Correct	221 ms	6092 KB	Output is correct
60	Runtime error	35 ms	12032 KB	Execution killed with signal 11
61	Correct	142 ms	6140 KB	Output is correct
62	Correct	255 ms	6124 KB	Output is correct
63	Runtime error	204 ms	12104 KB	Execution killed with signal 11
64	Runtime error	160 ms	12100 KB	Execution killed with signal 11
65	Runtime error	174 ms	12104 KB	Execution killed with signal 11
66	Runtime error	171 ms	12068 KB	Execution killed with signal 11
67	Runtime error	216 ms	12104 KB	Execution killed with signal 11
68	Runtime error	248 ms	12044 KB	Execution killed with signal 11
69	Runtime error	242 ms	11940 KB	Execution killed with signal 11
70	Runtime error	255 ms	12068 KB	Execution killed with signal 11
71	Correct	316 ms	6136 KB	Output is correct
72	Correct	295 ms	6152 KB	Output is correct
73	Correct	282 ms	6156 KB	Output is correct
74	Runtime error	170 ms	12124 KB	Execution killed with signal 11
75	Runtime error	175 ms	12072 KB	Execution killed with signal 11
76	Runtime error	175 ms	12028 KB	Execution killed with signal 11
77	Runtime error	180 ms	12044 KB	Execution killed with signal 11
78	Incorrect	292 ms	6148 KB	Output isn't correct
79	Correct	292 ms	6160 KB	Output is correct
80	Correct	292 ms	6164 KB	Output is correct
81	Correct	316 ms	6152 KB	Output is correct
82	Correct	337 ms	6160 KB	Output is correct
83	Runtime error	183 ms	12184 KB	Execution killed with signal 11
84	Correct	336 ms	6036 KB	Output is correct
85	Correct	332 ms	6388 KB	Output is correct
86	Correct	345 ms	6160 KB	Output is correct
87	Correct	320 ms	6172 KB	Output is correct
88	Runtime error	164 ms	12016 KB	Execution killed with signal 11
89	Correct	368 ms	6148 KB	Output is correct
90	Correct	350 ms	6152 KB	Output is correct
91	Correct	339 ms	6156 KB	Output is correct
92	Correct	345 ms	6096 KB	Output is correct