Submission #815965

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
815965	2023-08-09T03:02:39 Z	hieupham1103	Mecho (IOI09_mecho)	C++17	11 / 100	57 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] << ' ';
    // }

}

bool 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 + 1))){
                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++){
    //         if (visited[a[i][j]] == -1){
    //             cout << "* ";
    //             continue;
    //         }
    //         cout << visited[a[i][j]] << ' ';
    //     }
    //     cout << endl;
    // }
    // cout << endl;
    // for (int i = 1; i <= n; i++){
    //     for (int j = 1; j <= n; j++){
    //         if (timeBee[a[i][j]] == -1){
    //             cout << "* ";
    //             continue;
    //         }
    //         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 + 1)){
            ans = max(ans, mid);
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
    }
    
    // ans = check(2);

    cout << ans;

    return 0;
}

Subtask #1

11.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	35 ms	62932 KB	Output isn't correct
2	Incorrect	35 ms	62920 KB	Output isn't correct
3	Correct	35 ms	62872 KB	Output is correct
4	Incorrect	38 ms	62960 KB	Output isn't correct
5	Incorrect	39 ms	62932 KB	Output isn't correct
6	Incorrect	35 ms	62908 KB	Output isn't correct
7	Runtime error	39 ms	65536 KB	Execution killed with signal 9
8	Incorrect	35 ms	63052 KB	Output isn't correct
9	Incorrect	36 ms	63044 KB	Output isn't correct
10	Incorrect	36 ms	63092 KB	Output isn't correct
11	Incorrect	38 ms	62940 KB	Output isn't correct
12	Incorrect	36 ms	63964 KB	Output isn't correct
13	Incorrect	36 ms	63704 KB	Output isn't correct
14	Incorrect	36 ms	63980 KB	Output isn't correct
15	Incorrect	36 ms	63060 KB	Output isn't correct
16	Correct	39 ms	63108 KB	Output is correct
17	Incorrect	36 ms	63144 KB	Output isn't correct
18	Correct	35 ms	63200 KB	Output is correct
19	Incorrect	36 ms	63184 KB	Output isn't correct
20	Correct	38 ms	63216 KB	Output is correct
21	Incorrect	35 ms	63444 KB	Output isn't correct
22	Correct	35 ms	63452 KB	Output is correct
23	Incorrect	34 ms	63676 KB	Output isn't correct
24	Correct	35 ms	63644 KB	Output is correct
25	Incorrect	36 ms	63968 KB	Output isn't correct
26	Correct	37 ms	63940 KB	Output is correct
27	Incorrect	42 ms	64208 KB	Output isn't correct
28	Correct	43 ms	64124 KB	Output is correct
29	Incorrect	41 ms	64240 KB	Output isn't correct
30	Correct	38 ms	64296 KB	Output is correct
31	Incorrect	38 ms	64420 KB	Output isn't correct
32	Correct	37 ms	64456 KB	Output is correct
33	Runtime error	42 ms	65536 KB	Execution killed with signal 9
34	Runtime error	41 ms	65536 KB	Execution killed with signal 9
35	Runtime error	42 ms	65536 KB	Execution killed with signal 9
36	Runtime error	41 ms	65536 KB	Execution killed with signal 9
37	Runtime error	41 ms	65536 KB	Execution killed with signal 9
38	Runtime error	45 ms	65536 KB	Execution killed with signal 9
39	Runtime error	42 ms	65536 KB	Execution killed with signal 9
40	Runtime error	43 ms	65536 KB	Execution killed with signal 9
41	Runtime error	40 ms	65536 KB	Execution killed with signal 9
42	Runtime error	38 ms	65536 KB	Execution killed with signal 9
43	Runtime error	37 ms	65536 KB	Execution killed with signal 9
44	Runtime error	47 ms	65536 KB	Execution killed with signal 9
45	Runtime error	56 ms	65536 KB	Execution killed with signal 9
46	Runtime error	35 ms	65536 KB	Execution killed with signal 9
47	Runtime error	39 ms	65536 KB	Execution killed with signal 9
48	Runtime error	49 ms	65536 KB	Execution killed with signal 9
49	Runtime error	56 ms	65536 KB	Execution killed with signal 9
50	Runtime error	38 ms	65536 KB	Execution killed with signal 9
51	Runtime error	47 ms	65536 KB	Execution killed with signal 9
52	Runtime error	46 ms	65536 KB	Execution killed with signal 9
53	Runtime error	37 ms	65536 KB	Execution killed with signal 9
54	Runtime error	37 ms	65536 KB	Execution killed with signal 9
55	Runtime error	39 ms	65536 KB	Execution killed with signal 9
56	Runtime error	42 ms	65536 KB	Execution killed with signal 9
57	Runtime error	33 ms	65536 KB	Execution killed with signal 9
58	Runtime error	32 ms	65536 KB	Execution killed with signal 9
59	Runtime error	32 ms	65536 KB	Execution killed with signal 9
60	Runtime error	32 ms	65536 KB	Execution killed with signal 9
61	Runtime error	34 ms	65536 KB	Execution killed with signal 9
62	Runtime error	31 ms	65536 KB	Execution killed with signal 9
63	Runtime error	34 ms	65536 KB	Execution killed with signal 9
64	Runtime error	42 ms	65536 KB	Execution killed with signal 9
65	Runtime error	41 ms	65536 KB	Execution killed with signal 9
66	Runtime error	43 ms	65536 KB	Execution killed with signal 9
67	Runtime error	36 ms	65536 KB	Execution killed with signal 9
68	Runtime error	48 ms	65536 KB	Execution killed with signal 9
69	Runtime error	43 ms	65536 KB	Execution killed with signal 9
70	Runtime error	41 ms	65536 KB	Execution killed with signal 9
71	Runtime error	39 ms	65536 KB	Execution killed with signal 9
72	Runtime error	39 ms	65536 KB	Execution killed with signal 9
73	Runtime error	32 ms	65536 KB	Execution killed with signal 9
74	Runtime error	32 ms	65536 KB	Execution killed with signal 9
75	Runtime error	36 ms	65536 KB	Execution killed with signal 9
76	Runtime error	45 ms	65536 KB	Execution killed with signal 9
77	Runtime error	32 ms	65536 KB	Execution killed with signal 9
78	Runtime error	37 ms	65536 KB	Execution killed with signal 9
79	Runtime error	34 ms	65536 KB	Execution killed with signal 9
80	Runtime error	38 ms	65536 KB	Execution killed with signal 9
81	Runtime error	36 ms	65536 KB	Execution killed with signal 9
82	Runtime error	34 ms	65536 KB	Execution killed with signal 9
83	Runtime error	37 ms	65536 KB	Execution killed with signal 9
84	Runtime error	57 ms	65536 KB	Execution killed with signal 9
85	Runtime error	38 ms	65536 KB	Execution killed with signal 9
86	Runtime error	38 ms	65536 KB	Execution killed with signal 9
87	Runtime error	40 ms	65536 KB	Execution killed with signal 9
88	Runtime error	40 ms	65536 KB	Execution killed with signal 9
89	Runtime error	37 ms	65536 KB	Execution killed with signal 9
90	Runtime error	54 ms	65536 KB	Execution killed with signal 9
91	Runtime error	45 ms	65536 KB	Execution killed with signal 9
92	Runtime error	38 ms	65536 KB	Execution killed with signal 9