Submission #612511

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
612511	2022-07-29T16:18:54 Z	hieupham1103	Mecho (IOI09_mecho)	C++17	34 / 100	56 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 = 0;
int End = 0;
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	40 ms	62908 KB	Output is correct
2	Incorrect	43 ms	62976 KB	Output isn't correct
3	Correct	41 ms	62944 KB	Output is correct
4	Incorrect	46 ms	62952 KB	Output isn't correct
5	Correct	46 ms	62932 KB	Output is correct
6	Incorrect	47 ms	62952 KB	Output isn't correct
7	Runtime error	41 ms	65536 KB	Execution killed with signal 9
8	Correct	44 ms	63060 KB	Output is correct
9	Correct	43 ms	62924 KB	Output is correct
10	Correct	45 ms	63060 KB	Output is correct
11	Correct	53 ms	63052 KB	Output is correct
12	Incorrect	48 ms	63948 KB	Output isn't correct
13	Correct	44 ms	63748 KB	Output is correct
14	Correct	44 ms	63920 KB	Output is correct
15	Correct	43 ms	63060 KB	Output is correct
16	Correct	45 ms	63044 KB	Output is correct
17	Correct	51 ms	63104 KB	Output is correct
18	Correct	48 ms	63188 KB	Output is correct
19	Correct	50 ms	63256 KB	Output is correct
20	Correct	42 ms	63232 KB	Output is correct
21	Correct	44 ms	63472 KB	Output is correct
22	Correct	46 ms	63444 KB	Output is correct
23	Correct	48 ms	63696 KB	Output is correct
24	Correct	55 ms	63668 KB	Output is correct
25	Correct	42 ms	63908 KB	Output is correct
26	Correct	43 ms	63856 KB	Output is correct
27	Correct	43 ms	64132 KB	Output is correct
28	Correct	56 ms	64128 KB	Output is correct
29	Correct	50 ms	64200 KB	Output is correct
30	Correct	45 ms	64296 KB	Output is correct
31	Correct	43 ms	64460 KB	Output is correct
32	Correct	44 ms	64468 KB	Output is correct
33	Runtime error	44 ms	65536 KB	Execution killed with signal 9
34	Runtime error	46 ms	65536 KB	Execution killed with signal 9
35	Runtime error	50 ms	65536 KB	Execution killed with signal 9
36	Runtime error	49 ms	65536 KB	Execution killed with signal 9
37	Runtime error	45 ms	65536 KB	Execution killed with signal 9
38	Runtime error	48 ms	65536 KB	Execution killed with signal 9
39	Runtime error	49 ms	65536 KB	Execution killed with signal 9
40	Runtime error	48 ms	65536 KB	Execution killed with signal 9
41	Runtime error	44 ms	65536 KB	Execution killed with signal 9
42	Runtime error	48 ms	65536 KB	Execution killed with signal 9
43	Runtime error	48 ms	65536 KB	Execution killed with signal 9
44	Runtime error	46 ms	65536 KB	Execution killed with signal 9
45	Runtime error	49 ms	65536 KB	Execution killed with signal 9
46	Runtime error	55 ms	65536 KB	Execution killed with signal 9
47	Runtime error	47 ms	65536 KB	Execution killed with signal 9
48	Runtime error	44 ms	65536 KB	Execution killed with signal 9
49	Runtime error	50 ms	65536 KB	Execution killed with signal 9
50	Runtime error	49 ms	65536 KB	Execution killed with signal 9
51	Runtime error	47 ms	65536 KB	Execution killed with signal 9
52	Runtime error	48 ms	65536 KB	Execution killed with signal 9
53	Runtime error	41 ms	65536 KB	Execution killed with signal 9
54	Runtime error	45 ms	65536 KB	Execution killed with signal 9
55	Runtime error	40 ms	65536 KB	Execution killed with signal 9
56	Runtime error	39 ms	65536 KB	Execution killed with signal 9
57	Runtime error	47 ms	65536 KB	Execution killed with signal 9
58	Runtime error	38 ms	65536 KB	Execution killed with signal 9
59	Runtime error	43 ms	65536 KB	Execution killed with signal 9
60	Runtime error	47 ms	65536 KB	Execution killed with signal 9
61	Runtime error	44 ms	65536 KB	Execution killed with signal 9
62	Runtime error	42 ms	65536 KB	Execution killed with signal 9
63	Runtime error	45 ms	65536 KB	Execution killed with signal 9
64	Runtime error	51 ms	65536 KB	Execution killed with signal 9
65	Runtime error	44 ms	65536 KB	Execution killed with signal 9
66	Runtime error	43 ms	65536 KB	Execution killed with signal 9
67	Runtime error	48 ms	65536 KB	Execution killed with signal 9
68	Runtime error	46 ms	65536 KB	Execution killed with signal 9
69	Runtime error	50 ms	65536 KB	Execution killed with signal 9
70	Runtime error	46 ms	65536 KB	Execution killed with signal 9
71	Runtime error	44 ms	65536 KB	Execution killed with signal 9
72	Runtime error	41 ms	65536 KB	Execution killed with signal 9
73	Runtime error	40 ms	65536 KB	Execution killed with signal 9
74	Runtime error	45 ms	65536 KB	Execution killed with signal 9
75	Runtime error	42 ms	65536 KB	Execution killed with signal 9
76	Runtime error	47 ms	65536 KB	Execution killed with signal 9
77	Runtime error	42 ms	65536 KB	Execution killed with signal 9
78	Runtime error	38 ms	65536 KB	Execution killed with signal 9
79	Runtime error	40 ms	65536 KB	Execution killed with signal 9
80	Runtime error	39 ms	65536 KB	Execution killed with signal 9
81	Runtime error	44 ms	65536 KB	Execution killed with signal 9
82	Runtime error	39 ms	65536 KB	Execution killed with signal 9
83	Runtime error	43 ms	65536 KB	Execution killed with signal 9
84	Runtime error	39 ms	65536 KB	Execution killed with signal 9
85	Runtime error	37 ms	65536 KB	Execution killed with signal 9
86	Runtime error	41 ms	65536 KB	Execution killed with signal 9
87	Runtime error	41 ms	65536 KB	Execution killed with signal 9
88	Runtime error	41 ms	65536 KB	Execution killed with signal 9
89	Runtime error	39 ms	65536 KB	Execution killed with signal 9
90	Runtime error	37 ms	65536 KB	Execution killed with signal 9
91	Runtime error	36 ms	65536 KB	Execution killed with signal 9
92	Runtime error	40 ms	65536 KB	Execution killed with signal 9