Submission #612499

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
612499	2022-07-29T16:06:29 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};
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 < 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){
    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	51 ms	62956 KB	Output is correct
2	Incorrect	42 ms	62960 KB	Output isn't correct
3	Correct	44 ms	62920 KB	Output is correct
4	Incorrect	44 ms	62880 KB	Output isn't correct
5	Correct	53 ms	62980 KB	Output is correct
6	Incorrect	37 ms	63008 KB	Output isn't correct
7	Runtime error	45 ms	65536 KB	Execution killed with signal 9
8	Correct	47 ms	63108 KB	Output is correct
9	Correct	46 ms	62960 KB	Output is correct
10	Correct	43 ms	63048 KB	Output is correct
11	Correct	42 ms	63060 KB	Output is correct
12	Incorrect	44 ms	63868 KB	Output isn't correct
13	Correct	35 ms	63612 KB	Output is correct
14	Correct	46 ms	63992 KB	Output is correct
15	Correct	54 ms	63112 KB	Output is correct
16	Correct	46 ms	63112 KB	Output is correct
17	Correct	51 ms	63176 KB	Output is correct
18	Correct	52 ms	63172 KB	Output is correct
19	Correct	41 ms	63188 KB	Output is correct
20	Correct	43 ms	63228 KB	Output is correct
21	Correct	51 ms	63432 KB	Output is correct
22	Correct	53 ms	63404 KB	Output is correct
23	Correct	39 ms	63648 KB	Output is correct
24	Correct	47 ms	63612 KB	Output is correct
25	Correct	58 ms	63960 KB	Output is correct
26	Correct	46 ms	63896 KB	Output is correct
27	Correct	49 ms	64120 KB	Output is correct
28	Correct	54 ms	64092 KB	Output is correct
29	Correct	46 ms	64212 KB	Output is correct
30	Correct	57 ms	64292 KB	Output is correct
31	Correct	54 ms	64460 KB	Output is correct
32	Correct	52 ms	64460 KB	Output is correct
33	Runtime error	53 ms	65536 KB	Execution killed with signal 9
34	Runtime error	49 ms	65536 KB	Execution killed with signal 9
35	Runtime error	52 ms	65536 KB	Execution killed with signal 9
36	Runtime error	45 ms	65536 KB	Execution killed with signal 9
37	Runtime error	51 ms	65536 KB	Execution killed with signal 9
38	Runtime error	53 ms	65536 KB	Execution killed with signal 9
39	Runtime error	53 ms	65536 KB	Execution killed with signal 9
40	Runtime error	59 ms	65536 KB	Execution killed with signal 9
41	Runtime error	48 ms	65536 KB	Execution killed with signal 9
42	Runtime error	43 ms	65536 KB	Execution killed with signal 9
43	Runtime error	53 ms	65536 KB	Execution killed with signal 9
44	Runtime error	46 ms	65536 KB	Execution killed with signal 9
45	Runtime error	53 ms	65536 KB	Execution killed with signal 9
46	Runtime error	51 ms	65536 KB	Execution killed with signal 9
47	Runtime error	48 ms	65536 KB	Execution killed with signal 9
48	Runtime error	43 ms	65536 KB	Execution killed with signal 9
49	Runtime error	45 ms	65536 KB	Execution killed with signal 9
50	Runtime error	47 ms	65536 KB	Execution killed with signal 9
51	Runtime error	41 ms	65536 KB	Execution killed with signal 9
52	Runtime error	54 ms	65536 KB	Execution killed with signal 9
53	Runtime error	43 ms	65536 KB	Execution killed with signal 9
54	Runtime error	38 ms	65536 KB	Execution killed with signal 9
55	Runtime error	42 ms	65536 KB	Execution killed with signal 9
56	Runtime error	38 ms	65536 KB	Execution killed with signal 9
57	Runtime error	47 ms	65536 KB	Execution killed with signal 9
58	Runtime error	50 ms	65536 KB	Execution killed with signal 9
59	Runtime error	42 ms	65536 KB	Execution killed with signal 9
60	Runtime error	37 ms	65536 KB	Execution killed with signal 9
61	Runtime error	49 ms	65536 KB	Execution killed with signal 9
62	Runtime error	37 ms	65536 KB	Execution killed with signal 9
63	Runtime error	54 ms	65536 KB	Execution killed with signal 9
64	Runtime error	44 ms	65536 KB	Execution killed with signal 9
65	Runtime error	48 ms	65536 KB	Execution killed with signal 9
66	Runtime error	45 ms	65536 KB	Execution killed with signal 9
67	Runtime error	47 ms	65536 KB	Execution killed with signal 9
68	Runtime error	50 ms	65536 KB	Execution killed with signal 9
69	Runtime error	48 ms	65536 KB	Execution killed with signal 9
70	Runtime error	51 ms	65536 KB	Execution killed with signal 9
71	Runtime error	46 ms	65536 KB	Execution killed with signal 9
72	Runtime error	53 ms	65536 KB	Execution killed with signal 9
73	Runtime error	38 ms	65536 KB	Execution killed with signal 9
74	Runtime error	49 ms	65536 KB	Execution killed with signal 9
75	Runtime error	40 ms	65536 KB	Execution killed with signal 9
76	Runtime error	43 ms	65536 KB	Execution killed with signal 9
77	Runtime error	43 ms	65536 KB	Execution killed with signal 9
78	Runtime error	43 ms	65536 KB	Execution killed with signal 9
79	Runtime error	46 ms	65536 KB	Execution killed with signal 9
80	Runtime error	43 ms	65536 KB	Execution killed with signal 9
81	Runtime error	43 ms	65536 KB	Execution killed with signal 9
82	Runtime error	38 ms	65536 KB	Execution killed with signal 9
83	Runtime error	42 ms	65536 KB	Execution killed with signal 9
84	Runtime error	41 ms	65536 KB	Execution killed with signal 9
85	Runtime error	42 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	40 ms	65536 KB	Execution killed with signal 9
89	Runtime error	42 ms	65536 KB	Execution killed with signal 9
90	Runtime error	42 ms	65536 KB	Execution killed with signal 9
91	Runtime error	43 ms	65536 KB	Execution killed with signal 9
92	Runtime error	39 ms	65536 KB	Execution killed with signal 9