답안 #1072159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1072159	2024-08-23T15:05:05 Z	7again	Mecho (IOI09_mecho)	C++17	5 / 100	348 ms	12796 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}) ;
            }
        }
    }
    for(int i = 0 ; i < 4 ; i++){
        int x = Honey.first + dx[i] ;
        int y = Honey.second + dy[i] ;
        if(inside(x , y) && val(mn[x][y] , mn2[x][y]  - time))
            return true ;
    }

    return  false ;
}
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	0 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	0 ms	348 KB	Execution killed with signal 11
7	Runtime error	348 ms	12584 KB	Execution killed with signal 11
8	Runtime error	1 ms	600 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	0 ms	604 KB	Execution killed with signal 11
12	Runtime error	1 ms	604 KB	Execution killed with signal 11
13	Correct	1 ms	344 KB	Output is correct
14	Incorrect	1 ms	348 KB	Output isn't correct
15	Runtime error	0 ms	604 KB	Execution killed with signal 11
16	Runtime error	1 ms	604 KB	Execution killed with signal 11
17	Runtime error	1 ms	604 KB	Execution killed with signal 11
18	Runtime error	1 ms	604 KB	Execution killed with signal 11
19	Runtime error	1 ms	484 KB	Execution killed with signal 11
20	Runtime error	1 ms	604 KB	Execution killed with signal 11
21	Runtime error	1 ms	600 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	600 KB	Execution killed with signal 11
25	Runtime error	1 ms	604 KB	Execution killed with signal 11
26	Runtime error	2 ms	700 KB	Execution killed with signal 11
27	Runtime error	1 ms	600 KB	Execution killed with signal 11
28	Runtime error	1 ms	604 KB	Execution killed with signal 11
29	Runtime error	1 ms	704 KB	Execution killed with signal 11
30	Runtime error	2 ms	724 KB	Execution killed with signal 11
31	Runtime error	1 ms	700 KB	Execution killed with signal 11
32	Runtime error	2 ms	600 KB	Execution killed with signal 11
33	Runtime error	9 ms	3080 KB	Execution killed with signal 11
34	Runtime error	14 ms	2996 KB	Execution killed with signal 11
35	Runtime error	21 ms	3072 KB	Execution killed with signal 11
36	Runtime error	10 ms	3780 KB	Execution killed with signal 11
37	Runtime error	11 ms	3716 KB	Execution killed with signal 11
38	Runtime error	48 ms	3888 KB	Execution killed with signal 11
39	Runtime error	14 ms	4752 KB	Execution killed with signal 11
40	Runtime error	23 ms	4548 KB	Execution killed with signal 11
41	Runtime error	44 ms	4692 KB	Execution killed with signal 11
42	Runtime error	15 ms	5648 KB	Execution killed with signal 11
43	Runtime error	25 ms	5548 KB	Execution killed with signal 11
44	Runtime error	42 ms	5540 KB	Execution killed with signal 11
45	Runtime error	18 ms	6520 KB	Execution killed with signal 11
46	Runtime error	20 ms	6556 KB	Execution killed with signal 11
47	Runtime error	98 ms	6452 KB	Execution killed with signal 11
48	Runtime error	22 ms	7584 KB	Execution killed with signal 11
49	Runtime error	23 ms	7672 KB	Execution killed with signal 11
50	Runtime error	68 ms	7524 KB	Execution killed with signal 11
51	Runtime error	28 ms	8612 KB	Execution killed with signal 11
52	Runtime error	29 ms	8760 KB	Execution killed with signal 11
53	Runtime error	91 ms	8680 KB	Execution killed with signal 11
54	Runtime error	30 ms	9896 KB	Execution killed with signal 11
55	Runtime error	35 ms	9972 KB	Execution killed with signal 11
56	Runtime error	135 ms	9964 KB	Execution killed with signal 11
57	Runtime error	30 ms	11128 KB	Execution killed with signal 11
58	Runtime error	48 ms	11208 KB	Execution killed with signal 11
59	Runtime error	108 ms	11332 KB	Execution killed with signal 11
60	Runtime error	42 ms	12556 KB	Execution killed with signal 11
61	Runtime error	43 ms	12596 KB	Execution killed with signal 11
62	Runtime error	146 ms	12556 KB	Execution killed with signal 11
63	Runtime error	178 ms	12540 KB	Execution killed with signal 11
64	Incorrect	300 ms	6760 KB	Output isn't correct
65	Runtime error	136 ms	12640 KB	Execution killed with signal 11
66	Runtime error	141 ms	12548 KB	Execution killed with signal 11
67	Runtime error	174 ms	12516 KB	Execution killed with signal 11
68	Incorrect	311 ms	6764 KB	Output isn't correct
69	Incorrect	311 ms	6740 KB	Output isn't correct
70	Incorrect	302 ms	6752 KB	Output isn't correct
71	Incorrect	299 ms	6748 KB	Output isn't correct
72	Runtime error	223 ms	12612 KB	Execution killed with signal 11
73	Runtime error	295 ms	12748 KB	Execution killed with signal 11
74	Runtime error	181 ms	12680 KB	Execution killed with signal 11
75	Runtime error	182 ms	12696 KB	Execution killed with signal 11
76	Runtime error	176 ms	12620 KB	Execution killed with signal 11
77	Runtime error	175 ms	12724 KB	Execution killed with signal 11
78	Incorrect	287 ms	6764 KB	Output isn't correct
79	Incorrect	277 ms	6796 KB	Output isn't correct
80	Incorrect	265 ms	6780 KB	Output isn't correct
81	Incorrect	270 ms	6908 KB	Output isn't correct
82	Incorrect	271 ms	6784 KB	Output isn't correct
83	Runtime error	172 ms	12796 KB	Execution killed with signal 11
84	Incorrect	271 ms	6788 KB	Output isn't correct
85	Incorrect	304 ms	6776 KB	Output isn't correct
86	Incorrect	266 ms	6776 KB	Output isn't correct
87	Incorrect	300 ms	6784 KB	Output isn't correct
88	Runtime error	170 ms	12684 KB	Execution killed with signal 11
89	Incorrect	263 ms	6780 KB	Output isn't correct
90	Incorrect	263 ms	6872 KB	Output isn't correct
91	Incorrect	269 ms	6788 KB	Output isn't correct
92	Incorrect	288 ms	6780 KB	Output isn't correct