Submission #612497

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
612497	2022-07-29T16:05:07 Z	hieupham1103	Mecho (IOI09_mecho)	C++17	34 / 100	59 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;

int n, s;
int a[maxN][maxN];
ii b[maxN * maxN];
int grid[maxN * maxN];
int Start = -1;
int End = -1;
set <int> adj[maxN * maxN];
vector <int> listHive;
int timeBee[maxN * maxN];
int visited[maxN * maxN] = {0};

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(){
    queue <int> myQueue;
    for (int i = 0; i < maxN * maxN; 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){
    queue <int> myQueue;
    for (int i = 0; i < maxN * maxN; 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);            
                }
            }
        }
    }

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

    // for (int i = 1; i<= countCell; i++){
    //     cout << "#" << i << ":" << grid[i] << endl;
    //     for (auto j: adj[i]){
    //         cout << j << ' ';
    //     }
    //     cout << endl;
    // }

    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	62960 KB	Output is correct
2	Incorrect	39 ms	63052 KB	Output isn't correct
3	Correct	51 ms	62968 KB	Output is correct
4	Incorrect	43 ms	62976 KB	Output isn't correct
5	Correct	44 ms	62988 KB	Output is correct
6	Incorrect	43 ms	62908 KB	Output isn't correct
7	Runtime error	40 ms	65536 KB	Execution killed with signal 9
8	Correct	40 ms	63060 KB	Output is correct
9	Correct	41 ms	63040 KB	Output is correct
10	Correct	40 ms	63060 KB	Output is correct
11	Correct	45 ms	63036 KB	Output is correct
12	Incorrect	55 ms	63964 KB	Output isn't correct
13	Correct	52 ms	63700 KB	Output is correct
14	Correct	48 ms	63956 KB	Output is correct
15	Correct	41 ms	63100 KB	Output is correct
16	Correct	43 ms	63112 KB	Output is correct
17	Correct	41 ms	63052 KB	Output is correct
18	Correct	51 ms	63172 KB	Output is correct
19	Correct	47 ms	63232 KB	Output is correct
20	Correct	46 ms	63236 KB	Output is correct
21	Correct	41 ms	63408 KB	Output is correct
22	Correct	41 ms	63444 KB	Output is correct
23	Correct	42 ms	63588 KB	Output is correct
24	Correct	59 ms	63700 KB	Output is correct
25	Correct	49 ms	63964 KB	Output is correct
26	Correct	48 ms	63972 KB	Output is correct
27	Correct	45 ms	64016 KB	Output is correct
28	Correct	44 ms	64128 KB	Output is correct
29	Correct	43 ms	64288 KB	Output is correct
30	Correct	48 ms	64296 KB	Output is correct
31	Correct	45 ms	64360 KB	Output is correct
32	Correct	44 ms	64420 KB	Output is correct
33	Runtime error	49 ms	65536 KB	Execution killed with signal 9
34	Runtime error	54 ms	65536 KB	Execution killed with signal 9
35	Runtime error	47 ms	65536 KB	Execution killed with signal 9
36	Runtime error	47 ms	65536 KB	Execution killed with signal 9
37	Runtime error	48 ms	65536 KB	Execution killed with signal 9
38	Runtime error	58 ms	65536 KB	Execution killed with signal 9
39	Runtime error	48 ms	65536 KB	Execution killed with signal 9
40	Runtime error	56 ms	65536 KB	Execution killed with signal 9
41	Runtime error	45 ms	65536 KB	Execution killed with signal 9
42	Runtime error	55 ms	65536 KB	Execution killed with signal 9
43	Runtime error	44 ms	65536 KB	Execution killed with signal 9
44	Runtime error	42 ms	65536 KB	Execution killed with signal 9
45	Runtime error	43 ms	65536 KB	Execution killed with signal 9
46	Runtime error	46 ms	65536 KB	Execution killed with signal 9
47	Runtime error	44 ms	65536 KB	Execution killed with signal 9
48	Runtime error	42 ms	65536 KB	Execution killed with signal 9
49	Runtime error	52 ms	65536 KB	Execution killed with signal 9
50	Runtime error	42 ms	65536 KB	Execution killed with signal 9
51	Runtime error	41 ms	65536 KB	Execution killed with signal 9
52	Runtime error	45 ms	65536 KB	Execution killed with signal 9
53	Runtime error	52 ms	65536 KB	Execution killed with signal 9
54	Runtime error	43 ms	65536 KB	Execution killed with signal 9
55	Runtime error	41 ms	65536 KB	Execution killed with signal 9
56	Runtime error	42 ms	65536 KB	Execution killed with signal 9
57	Runtime error	41 ms	65536 KB	Execution killed with signal 9
58	Runtime error	38 ms	65536 KB	Execution killed with signal 9
59	Runtime error	44 ms	65536 KB	Execution killed with signal 9
60	Runtime error	45 ms	65536 KB	Execution killed with signal 9
61	Runtime error	51 ms	65536 KB	Execution killed with signal 9
62	Runtime error	43 ms	65536 KB	Execution killed with signal 9
63	Runtime error	43 ms	65536 KB	Execution killed with signal 9
64	Runtime error	46 ms	65536 KB	Execution killed with signal 9
65	Runtime error	42 ms	65536 KB	Execution killed with signal 9
66	Runtime error	41 ms	65536 KB	Execution killed with signal 9
67	Runtime error	43 ms	65536 KB	Execution killed with signal 9
68	Runtime error	42 ms	65536 KB	Execution killed with signal 9
69	Runtime error	42 ms	65536 KB	Execution killed with signal 9
70	Runtime error	46 ms	65536 KB	Execution killed with signal 9
71	Runtime error	42 ms	65536 KB	Execution killed with signal 9
72	Runtime error	47 ms	65536 KB	Execution killed with signal 9
73	Runtime error	42 ms	65536 KB	Execution killed with signal 9
74	Runtime error	38 ms	65536 KB	Execution killed with signal 9
75	Runtime error	41 ms	65536 KB	Execution killed with signal 9
76	Runtime error	41 ms	65536 KB	Execution killed with signal 9
77	Runtime error	37 ms	65536 KB	Execution killed with signal 9
78	Runtime error	39 ms	65536 KB	Execution killed with signal 9
79	Runtime error	45 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	54 ms	65536 KB	Execution killed with signal 9
83	Runtime error	49 ms	65536 KB	Execution killed with signal 9
84	Runtime error	42 ms	65536 KB	Execution killed with signal 9
85	Runtime error	43 ms	65536 KB	Execution killed with signal 9
86	Runtime error	40 ms	65536 KB	Execution killed with signal 9
87	Runtime error	38 ms	65536 KB	Execution killed with signal 9
88	Runtime error	47 ms	65536 KB	Execution killed with signal 9
89	Runtime error	47 ms	65536 KB	Execution killed with signal 9
90	Runtime error	53 ms	65536 KB	Execution killed with signal 9
91	Runtime error	51 ms	65536 KB	Execution killed with signal 9
92	Runtime error	44 ms	65536 KB	Execution killed with signal 9