Submission #612494

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
612494	2022-07-29T16:00:53 Z	hieupham1103	Mecho (IOI09_mecho)	C++17	34 / 100	80 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 = 810;

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	23 ms	41428 KB	Output is correct
2	Incorrect	29 ms	41432 KB	Output isn't correct
3	Correct	28 ms	41548 KB	Output is correct
4	Incorrect	25 ms	41392 KB	Output isn't correct
5	Correct	23 ms	41392 KB	Output is correct
6	Incorrect	23 ms	41384 KB	Output isn't correct
7	Runtime error	63 ms	65536 KB	Execution killed with signal 9
8	Correct	31 ms	41512 KB	Output is correct
9	Correct	25 ms	41428 KB	Output is correct
10	Correct	27 ms	41420 KB	Output is correct
11	Correct	28 ms	41524 KB	Output is correct
12	Incorrect	28 ms	42316 KB	Output isn't correct
13	Correct	25 ms	42156 KB	Output is correct
14	Correct	25 ms	42352 KB	Output is correct
15	Correct	29 ms	41556 KB	Output is correct
16	Correct	23 ms	41556 KB	Output is correct
17	Correct	23 ms	41556 KB	Output is correct
18	Correct	31 ms	41648 KB	Output is correct
19	Correct	30 ms	41644 KB	Output is correct
20	Correct	30 ms	41712 KB	Output is correct
21	Correct	28 ms	41812 KB	Output is correct
22	Correct	26 ms	42008 KB	Output is correct
23	Correct	31 ms	42068 KB	Output is correct
24	Correct	29 ms	42108 KB	Output is correct
25	Correct	24 ms	42308 KB	Output is correct
26	Correct	31 ms	42324 KB	Output is correct
27	Correct	25 ms	42548 KB	Output is correct
28	Correct	25 ms	42580 KB	Output is correct
29	Correct	28 ms	42764 KB	Output is correct
30	Correct	26 ms	42676 KB	Output is correct
31	Correct	26 ms	42940 KB	Output is correct
32	Correct	27 ms	42928 KB	Output is correct
33	Runtime error	57 ms	65536 KB	Execution killed with signal 9
34	Runtime error	53 ms	65536 KB	Execution killed with signal 9
35	Runtime error	74 ms	65536 KB	Execution killed with signal 9
36	Runtime error	61 ms	65536 KB	Execution killed with signal 9
37	Runtime error	62 ms	65536 KB	Execution killed with signal 9
38	Runtime error	78 ms	65536 KB	Execution killed with signal 9
39	Runtime error	76 ms	65536 KB	Execution killed with signal 9
40	Runtime error	58 ms	65536 KB	Execution killed with signal 9
41	Runtime error	63 ms	65536 KB	Execution killed with signal 9
42	Runtime error	59 ms	65536 KB	Execution killed with signal 9
43	Runtime error	64 ms	65536 KB	Execution killed with signal 9
44	Runtime error	76 ms	65536 KB	Execution killed with signal 9
45	Runtime error	63 ms	65536 KB	Execution killed with signal 9
46	Runtime error	69 ms	65536 KB	Execution killed with signal 9
47	Runtime error	60 ms	65536 KB	Execution killed with signal 9
48	Runtime error	58 ms	65536 KB	Execution killed with signal 9
49	Runtime error	58 ms	65536 KB	Execution killed with signal 9
50	Runtime error	80 ms	65536 KB	Execution killed with signal 9
51	Runtime error	62 ms	65536 KB	Execution killed with signal 9
52	Runtime error	56 ms	65536 KB	Execution killed with signal 9
53	Runtime error	57 ms	65536 KB	Execution killed with signal 9
54	Runtime error	60 ms	65536 KB	Execution killed with signal 9
55	Runtime error	57 ms	65536 KB	Execution killed with signal 9
56	Runtime error	65 ms	65536 KB	Execution killed with signal 9
57	Runtime error	56 ms	65536 KB	Execution killed with signal 9
58	Runtime error	51 ms	65536 KB	Execution killed with signal 9
59	Runtime error	57 ms	65536 KB	Execution killed with signal 9
60	Runtime error	53 ms	65536 KB	Execution killed with signal 9
61	Runtime error	51 ms	65536 KB	Execution killed with signal 9
62	Runtime error	58 ms	65536 KB	Execution killed with signal 9
63	Runtime error	61 ms	65536 KB	Execution killed with signal 9
64	Runtime error	56 ms	65536 KB	Execution killed with signal 9
65	Runtime error	57 ms	65536 KB	Execution killed with signal 9
66	Runtime error	59 ms	65536 KB	Execution killed with signal 9
67	Runtime error	59 ms	65536 KB	Execution killed with signal 9
68	Runtime error	69 ms	65536 KB	Execution killed with signal 9
69	Runtime error	54 ms	65536 KB	Execution killed with signal 9
70	Runtime error	55 ms	65536 KB	Execution killed with signal 9
71	Runtime error	57 ms	65536 KB	Execution killed with signal 9
72	Runtime error	61 ms	65536 KB	Execution killed with signal 9
73	Runtime error	55 ms	65536 KB	Execution killed with signal 9
74	Runtime error	58 ms	65536 KB	Execution killed with signal 9
75	Runtime error	54 ms	65536 KB	Execution killed with signal 9
76	Runtime error	54 ms	65536 KB	Execution killed with signal 9
77	Runtime error	58 ms	65536 KB	Execution killed with signal 9
78	Runtime error	56 ms	65536 KB	Execution killed with signal 9
79	Runtime error	60 ms	65536 KB	Execution killed with signal 9
80	Runtime error	54 ms	65536 KB	Execution killed with signal 9
81	Runtime error	57 ms	65536 KB	Execution killed with signal 9
82	Runtime error	53 ms	65536 KB	Execution killed with signal 9
83	Runtime error	54 ms	65536 KB	Execution killed with signal 9
84	Runtime error	55 ms	65536 KB	Execution killed with signal 9
85	Runtime error	51 ms	65536 KB	Execution killed with signal 9
86	Runtime error	53 ms	65536 KB	Execution killed with signal 9
87	Runtime error	57 ms	65536 KB	Execution killed with signal 9
88	Runtime error	55 ms	65536 KB	Execution killed with signal 9
89	Runtime error	54 ms	65536 KB	Execution killed with signal 9
90	Runtime error	61 ms	65536 KB	Execution killed with signal 9
91	Runtime error	56 ms	65536 KB	Execution killed with signal 9
92	Runtime error	55 ms	65536 KB	Execution killed with signal 9