Submission #612508

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
612508	2022-07-29T16:17:28 Z	hieupham1103	Mecho (IOI09_mecho)	C++17	34 / 100	65 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 + 10][maxN + 10];
ii b[maxNN + 10];
int grid[maxNN + 10];
int Start = -1;
int End = -1;
set <int> adj[maxNN + 10];
vector <int> listHive;
int timeBee[maxNN + 10];
int visited[maxNN + 10];
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	61 ms	63012 KB	Output is correct
2	Incorrect	50 ms	62968 KB	Output isn't correct
3	Correct	59 ms	62860 KB	Output is correct
4	Incorrect	57 ms	63032 KB	Output isn't correct
5	Correct	58 ms	62988 KB	Output is correct
6	Incorrect	52 ms	63008 KB	Output isn't correct
7	Runtime error	40 ms	65536 KB	Execution killed with signal 9
8	Correct	48 ms	63020 KB	Output is correct
9	Correct	49 ms	63052 KB	Output is correct
10	Correct	52 ms	62964 KB	Output is correct
11	Correct	44 ms	62984 KB	Output is correct
12	Incorrect	48 ms	63976 KB	Output isn't correct
13	Correct	65 ms	63704 KB	Output is correct
14	Correct	42 ms	63940 KB	Output is correct
15	Correct	50 ms	63052 KB	Output is correct
16	Correct	49 ms	63092 KB	Output is correct
17	Correct	46 ms	63056 KB	Output is correct
18	Correct	45 ms	63176 KB	Output is correct
19	Correct	49 ms	63172 KB	Output is correct
20	Correct	48 ms	63316 KB	Output is correct
21	Correct	50 ms	63436 KB	Output is correct
22	Correct	49 ms	63408 KB	Output is correct
23	Correct	49 ms	63696 KB	Output is correct
24	Correct	42 ms	63696 KB	Output is correct
25	Correct	44 ms	63984 KB	Output is correct
26	Correct	46 ms	63968 KB	Output is correct
27	Correct	58 ms	64092 KB	Output is correct
28	Correct	57 ms	64124 KB	Output is correct
29	Correct	50 ms	64416 KB	Output is correct
30	Correct	48 ms	64208 KB	Output is correct
31	Correct	44 ms	64460 KB	Output is correct
32	Correct	43 ms	64436 KB	Output is correct
33	Runtime error	48 ms	65536 KB	Execution killed with signal 9
34	Runtime error	55 ms	65536 KB	Execution killed with signal 9
35	Runtime error	46 ms	65536 KB	Execution killed with signal 9
36	Runtime error	55 ms	65536 KB	Execution killed with signal 9
37	Runtime error	58 ms	65536 KB	Execution killed with signal 9
38	Runtime error	45 ms	65536 KB	Execution killed with signal 9
39	Runtime error	43 ms	65536 KB	Execution killed with signal 9
40	Runtime error	43 ms	65536 KB	Execution killed with signal 9
41	Runtime error	45 ms	65536 KB	Execution killed with signal 9
42	Runtime error	41 ms	65536 KB	Execution killed with signal 9
43	Runtime error	51 ms	65536 KB	Execution killed with signal 9
44	Runtime error	55 ms	65536 KB	Execution killed with signal 9
45	Runtime error	41 ms	65536 KB	Execution killed with signal 9
46	Runtime error	42 ms	65536 KB	Execution killed with signal 9
47	Runtime error	49 ms	65536 KB	Execution killed with signal 9
48	Runtime error	41 ms	65536 KB	Execution killed with signal 9
49	Runtime error	38 ms	65536 KB	Execution killed with signal 9
50	Runtime error	40 ms	65536 KB	Execution killed with signal 9
51	Runtime error	57 ms	65536 KB	Execution killed with signal 9
52	Runtime error	46 ms	65536 KB	Execution killed with signal 9
53	Runtime error	46 ms	65536 KB	Execution killed with signal 9
54	Runtime error	38 ms	65536 KB	Execution killed with signal 9
55	Runtime error	43 ms	65536 KB	Execution killed with signal 9
56	Runtime error	43 ms	65536 KB	Execution killed with signal 9
57	Runtime error	47 ms	65536 KB	Execution killed with signal 9
58	Runtime error	46 ms	65536 KB	Execution killed with signal 9
59	Runtime error	40 ms	65536 KB	Execution killed with signal 9
60	Runtime error	43 ms	65536 KB	Execution killed with signal 9
61	Runtime error	38 ms	65536 KB	Execution killed with signal 9
62	Runtime error	42 ms	65536 KB	Execution killed with signal 9
63	Runtime error	52 ms	65536 KB	Execution killed with signal 9
64	Runtime error	47 ms	65536 KB	Execution killed with signal 9
65	Runtime error	46 ms	65536 KB	Execution killed with signal 9
66	Runtime error	55 ms	65536 KB	Execution killed with signal 9
67	Runtime error	49 ms	65536 KB	Execution killed with signal 9
68	Runtime error	42 ms	65536 KB	Execution killed with signal 9
69	Runtime error	43 ms	65536 KB	Execution killed with signal 9
70	Runtime error	48 ms	65536 KB	Execution killed with signal 9
71	Runtime error	49 ms	65536 KB	Execution killed with signal 9
72	Runtime error	46 ms	65536 KB	Execution killed with signal 9
73	Runtime error	54 ms	65536 KB	Execution killed with signal 9
74	Runtime error	56 ms	65536 KB	Execution killed with signal 9
75	Runtime error	49 ms	65536 KB	Execution killed with signal 9
76	Runtime error	46 ms	65536 KB	Execution killed with signal 9
77	Runtime error	37 ms	65536 KB	Execution killed with signal 9
78	Runtime error	44 ms	65536 KB	Execution killed with signal 9
79	Runtime error	52 ms	65536 KB	Execution killed with signal 9
80	Runtime error	40 ms	65536 KB	Execution killed with signal 9
81	Runtime error	43 ms	65536 KB	Execution killed with signal 9
82	Runtime error	41 ms	65536 KB	Execution killed with signal 9
83	Runtime error	46 ms	65536 KB	Execution killed with signal 9
84	Runtime error	48 ms	65536 KB	Execution killed with signal 9
85	Runtime error	57 ms	65536 KB	Execution killed with signal 9
86	Runtime error	44 ms	65536 KB	Execution killed with signal 9
87	Runtime error	48 ms	65536 KB	Execution killed with signal 9
88	Runtime error	52 ms	65536 KB	Execution killed with signal 9
89	Runtime error	44 ms	65536 KB	Execution killed with signal 9
90	Runtime error	54 ms	65536 KB	Execution killed with signal 9
91	Runtime error	37 ms	65536 KB	Execution killed with signal 9
92	Runtime error	39 ms	65536 KB	Execution killed with signal 9