Submission #612504

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
612504	2022-07-29T16:12:13 Z	hieupham1103	Mecho (IOI09_mecho)	C++17	34 / 100	70 ms	65536 KB

mecho

#include<bits/stdc++.h>
#define ii pair <int,int>
#define fi first
#define se second
#define int long long
using namespace std;

const int maxN = 1000;
const int maxNN = maxN * maxN;

int n, s;
int a[maxN][maxN];
ii b[maxNN];
int grid[maxNN];
int Start = -1;
int End = -1;
set <int> adj[maxNN];
vector <int> listHive;
int timeBee[maxNN];
int visited[maxNN];
queue <int> myQueue;

vector <ii> dir = {
    {0,1},
    {1,0},
    {-1,0},
    {0,-1}
};

bool checkInside(int x, int y){
    if (x >= 1 and x <= n and y >= 1 and y <= n){
        return 1;
    }
    return 0;
}

void getBeeTime(){
    for (int i = 0; i < maxNN; i++){
        timeBee[i] = -1;
    }
    for (auto i: listHive){
        myQueue.push(i);
        timeBee[i] = 0;
    }

    while(!myQueue.empty()){
        int tempV = myQueue.front();
        myQueue.pop();
        // cout << tempV << ": ";
        for (auto newV: adj[tempV]){
            if (timeBee[newV] == -1 and grid[newV] == 0){
                timeBee[newV] = timeBee[tempV] + 1;
                myQueue.push(newV);
                // cout << newV << ' ';
            }
        }
        // cout << endl;
    }

    // for (int i = 0; i <= 50; i++){
    //     cout << timeBee[i] << ' ';
    // }

}

int check(int beginTime){
    for (int i = 0; i < maxNN; i++){
        visited[i] = -1;
    }
    myQueue.push(Start);
    visited[Start] = beginTime * s;

    if (timeBee[Start] <= beginTime){
        return 0;
    }

    while(!myQueue.empty()){
        int tempV = myQueue.front();
        myQueue.pop();
        // cout << tempV << ": ";
        for (auto newV: adj[tempV]){
            if (visited[newV] == -1 and grid[newV] == 0 and timeBee[newV] > ((visited[tempV] + 1) / s)){
                visited[newV] = visited[tempV] + 1;
                myQueue.push(newV);
                // cout << newV << "," << timeBee[newV] << "," << visited[newV] << "  ";
            }
        }
        // cout << endl;
    }

    // for (int i = 1; i <= n; i++){
    //     for (int j = 1; j <= n; j++){
    //         cout << visited[a[i][j]] / s << ' ';
    //     }
    //     cout << endl;
    // }
    // cout << endl;
    // for (int i = 1; i <= n; i++){
    //     for (int j = 1; j <= n; j++){
    //         cout << timeBee[a[i][j]] << ' ';
    //     }
    //     cout << endl;
    // }
    // cout << endl;

    if (visited[End] == -1){
        return 0;
    }
    return visited[End];
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> s;
    
    int countCell = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            countCell++;
            char inp;
            cin >> inp;
            a[i][j] = countCell;
            b[countCell] = {i,j};
            if (inp == 'T'){
                grid[countCell] = 1;
            }
            else if (inp == 'H'){
                grid[countCell] = 1;
                listHive.push_back(countCell);
            }
            else if (inp == 'M'){
                Start = countCell;
            }
            else if (inp == 'D'){
                End = countCell;
            }
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            int t = a[i][j];
            for (auto d: dir){
                int x = i + d.fi;
                int y = j + d.se;
                int n = a[x][y];
                if (checkInside(x, y)){
                    adj[t].insert(n);
                    adj[n].insert(t);            
                }
            }
        }
    }

    getBeeTime();

    int left = 0;
    int right = 1e8;
    int ans = -1;
    while(left <= right){
        int mid = (left + right) / 2;
        if (check(mid)){
            ans = max(ans, mid);
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
    }
    
    // ans = check(2);

    cout << ans;

    return 0;
}

Subtask #1

34.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	62976 KB	Output is correct
2	Incorrect	39 ms	62960 KB	Output isn't correct
3	Correct	41 ms	62932 KB	Output is correct
4	Incorrect	53 ms	62980 KB	Output isn't correct
5	Correct	54 ms	63052 KB	Output is correct
6	Incorrect	50 ms	63012 KB	Output isn't correct
7	Runtime error	39 ms	65536 KB	Execution killed with signal 9
8	Correct	40 ms	63020 KB	Output is correct
9	Correct	41 ms	63020 KB	Output is correct
10	Correct	42 ms	63060 KB	Output is correct
11	Correct	46 ms	63052 KB	Output is correct
12	Incorrect	47 ms	64100 KB	Output isn't correct
13	Correct	55 ms	63624 KB	Output is correct
14	Correct	70 ms	63972 KB	Output is correct
15	Correct	45 ms	63108 KB	Output is correct
16	Correct	40 ms	63116 KB	Output is correct
17	Correct	41 ms	63184 KB	Output is correct
18	Correct	41 ms	63168 KB	Output is correct
19	Correct	43 ms	63252 KB	Output is correct
20	Correct	41 ms	63180 KB	Output is correct
21	Correct	62 ms	63376 KB	Output is correct
22	Correct	58 ms	63420 KB	Output is correct
23	Correct	41 ms	63564 KB	Output is correct
24	Correct	42 ms	63652 KB	Output is correct
25	Correct	43 ms	63972 KB	Output is correct
26	Correct	44 ms	63964 KB	Output is correct
27	Correct	57 ms	64120 KB	Output is correct
28	Correct	57 ms	64124 KB	Output is correct
29	Correct	43 ms	64168 KB	Output is correct
30	Correct	40 ms	64284 KB	Output is correct
31	Correct	49 ms	64460 KB	Output is correct
32	Correct	44 ms	64420 KB	Output is correct
33	Runtime error	44 ms	65536 KB	Execution killed with signal 9
34	Runtime error	44 ms	65536 KB	Execution killed with signal 9
35	Runtime error	46 ms	65536 KB	Execution killed with signal 9
36	Runtime error	45 ms	65536 KB	Execution killed with signal 9
37	Runtime error	55 ms	65536 KB	Execution killed with signal 9
38	Runtime error	60 ms	65536 KB	Execution killed with signal 9
39	Runtime error	53 ms	65536 KB	Execution killed with signal 9
40	Runtime error	47 ms	65536 KB	Execution killed with signal 9
41	Runtime error	48 ms	65536 KB	Execution killed with signal 9
42	Runtime error	42 ms	65536 KB	Execution killed with signal 9
43	Runtime error	43 ms	65536 KB	Execution killed with signal 9
44	Runtime error	52 ms	65536 KB	Execution killed with signal 9
45	Runtime error	46 ms	65536 KB	Execution killed with signal 9
46	Runtime error	43 ms	65536 KB	Execution killed with signal 9
47	Runtime error	41 ms	65536 KB	Execution killed with signal 9
48	Runtime error	43 ms	65536 KB	Execution killed with signal 9
49	Runtime error	46 ms	65536 KB	Execution killed with signal 9
50	Runtime error	43 ms	65536 KB	Execution killed with signal 9
51	Runtime error	48 ms	65536 KB	Execution killed with signal 9
52	Runtime error	50 ms	65536 KB	Execution killed with signal 9
53	Runtime error	47 ms	65536 KB	Execution killed with signal 9
54	Runtime error	42 ms	65536 KB	Execution killed with signal 9
55	Runtime error	39 ms	65536 KB	Execution killed with signal 9
56	Runtime error	44 ms	65536 KB	Execution killed with signal 9
57	Runtime error	49 ms	65536 KB	Execution killed with signal 9
58	Runtime error	45 ms	65536 KB	Execution killed with signal 9
59	Runtime error	42 ms	65536 KB	Execution killed with signal 9
60	Runtime error	40 ms	65536 KB	Execution killed with signal 9
61	Runtime error	48 ms	65536 KB	Execution killed with signal 9
62	Runtime error	40 ms	65536 KB	Execution killed with signal 9
63	Runtime error	48 ms	65536 KB	Execution killed with signal 9
64	Runtime error	46 ms	65536 KB	Execution killed with signal 9
65	Runtime error	43 ms	65536 KB	Execution killed with signal 9
66	Runtime error	44 ms	65536 KB	Execution killed with signal 9
67	Runtime error	44 ms	65536 KB	Execution killed with signal 9
68	Runtime error	43 ms	65536 KB	Execution killed with signal 9
69	Runtime error	53 ms	65536 KB	Execution killed with signal 9
70	Runtime error	50 ms	65536 KB	Execution killed with signal 9
71	Runtime error	42 ms	65536 KB	Execution killed with signal 9
72	Runtime error	42 ms	65536 KB	Execution killed with signal 9
73	Runtime error	43 ms	65536 KB	Execution killed with signal 9
74	Runtime error	39 ms	65536 KB	Execution killed with signal 9
75	Runtime error	44 ms	65536 KB	Execution killed with signal 9
76	Runtime error	51 ms	65536 KB	Execution killed with signal 9
77	Runtime error	48 ms	65536 KB	Execution killed with signal 9
78	Runtime error	41 ms	65536 KB	Execution killed with signal 9
79	Runtime error	43 ms	65536 KB	Execution killed with signal 9
80	Runtime error	42 ms	65536 KB	Execution killed with signal 9
81	Runtime error	47 ms	65536 KB	Execution killed with signal 9
82	Runtime error	42 ms	65536 KB	Execution killed with signal 9
83	Runtime error	45 ms	65536 KB	Execution killed with signal 9
84	Runtime error	39 ms	65536 KB	Execution killed with signal 9
85	Runtime error	40 ms	65536 KB	Execution killed with signal 9
86	Runtime error	39 ms	65536 KB	Execution killed with signal 9
87	Runtime error	45 ms	65536 KB	Execution killed with signal 9
88	Runtime error	39 ms	65536 KB	Execution killed with signal 9
89	Runtime error	39 ms	65536 KB	Execution killed with signal 9
90	Runtime error	47 ms	65536 KB	Execution killed with signal 9
91	Runtime error	51 ms	65536 KB	Execution killed with signal 9
92	Runtime error	40 ms	65536 KB	Execution killed with signal 9