oj.uz

Submission #624562

# Submission time Handle Problem Language Result Execution time Memory
624562 2022-08-08T13:14:32 Z jackkkk Mecho (IOI09_mecho) C++11
4 / 100
 1000 ms 3284 KB 
// Mecho
// https://oj.uz/problem/view/IOI09_mecho

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <array>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <list>
#include <float.h>
#include <climits>
#include <cmath>

using namespace std;

void quit() {
    cout.flush();
    exit(0);
}
int n, s;
pair<int, int> st, dest;
bool tree[800][800]; //contains trees and grass. bee hives are also trees
bool tmp[800][800];
bool mecho_done[800][800];
deque<pair<int, int>> hives, mecho, tmp1, tmp2, new_hives, new_mecho;
pair<int, int> gto[4] = {{0,1}, {0,-1}, {-1,0}, {0,-1}};
bool in_grid(int a, int b){
    return a >= 0 && a < n && b >= 0 && b < n;
}
bool bee_can_go(int a, int b){
    return in_grid(a,b) && !(a == dest.first && b == dest.second) && !tree[a][b];
}
bool mecho_can_go(int a, int b){
    return in_grid(a, b) && !mecho_done[a][b] && !tree[a][b];
}
void bee_expand(){
    new_hives.clear();
    while(!hives.empty()){
        pair<int, int> curr = hives.front();
        int cx = curr.first, cy = curr.second;
        hives.pop_front();
        for(const auto &to : gto){
            int nx = to.first +cx, ny = to.second+cy;
            if(bee_can_go(nx, ny)){
                new_hives.emplace_back(nx, ny);
                tree[nx][ny]=1;
            }
        }
    }
    hives=new_hives;
}
bool finished;
bool mecho_expand(){
    //if can't expand anymore return false
    for(int i = 0; i < s; i++){
        new_mecho.clear();
        while(!mecho.empty()){
            pair<int, int> curr = mecho.front();
            int cx = curr.first, cy = curr.second;
            mecho.pop_front();
            for(const auto &to : gto){
                int nx = to.first +cx, ny = to.second+cy;
                if(mecho_can_go(nx, ny)){
                    new_mecho.emplace_back(nx, ny);
                    mecho_done[nx][ny]=1;                }
                if(nx == dest.first && ny == dest.second){
                    //can get to dest
                    finished=true;
                    return false;
                }
            }
        }
        mecho=new_mecho;
    }
    return mecho.size()>0;
}

bool good(int wait_time){
    tmp1 = hives;
    tmp2 = mecho;
    for(int i = 0; i < 800; i++){
        for(int j = 0; j < 800; j++){
            mecho_done[i][j]=0;
            tmp[i][j]=tree[i][j];
        }
    }
    mecho_done[st.first][st.second]=1;
    finished=false;

    //propogate until can't
    for(int i = 0; i < wait_time; i++){
        bee_expand();
    }

    while(mecho_expand()){
        bee_expand();
    }

    //reset variables
    for(int i = 0; i < 800; i++){
        for(int j = 0; j < 800; j++){
            tree[i][j]=tmp[i][j];
        }
    }
    hives=tmp1;
    mecho=tmp2;
    return finished;

}


int main(void){
    //freopen("qwer.in", "r", stdin);
    //freopen("qwer.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s;
    for(int i = 0; i < n; i++){
        string s; cin >> s;
        for(int j = 0; j < n; j++){
            if(s[j]=='T'){
                tree[i][j]=1;
            }
            else if(s[j]=='M'){
                st={i,j};
                mecho.emplace_back(i,j);
            }
            else if(s[j]=='D'){
                dest = {i,j};
            }
            else if(s[j] == 'H'){
                hives.emplace_back(i,j);
                tree[i][j]=1;
            }
        }
    }
    if(!good(0)){
        cout << "-1\n";
        quit();
    }
    int s = 0, e = 1e8;
    while(s != e){
        int md = (s+e+1)/2;
        if(good(md)){
            s=md;
        }
        else{
            e=md-1;
        }
    }
    cout << s << "\n";
    quit();
}

Subtask #1
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 2132 KB Time limit exceeded
2 Execution timed out 1093 ms 2132 KB Time limit exceeded
3 Execution timed out 1083 ms 2132 KB Time limit exceeded
4 Execution timed out 1081 ms 2132 KB Time limit exceeded
5 Incorrect 2 ms 2132 KB Output isn't correct
6 Incorrect 1 ms 2132 KB Output isn't correct
7 Incorrect 7 ms 2900 KB Output isn't correct
8 Execution timed out 1081 ms 2132 KB Time limit exceeded
9 Execution timed out 1085 ms 2132 KB Time limit exceeded
10 Execution timed out 1096 ms 2132 KB Time limit exceeded
11 Execution timed out 1095 ms 2132 KB Time limit exceeded
12 Execution timed out 1088 ms 2132 KB Time limit exceeded
13 Execution timed out 1097 ms 2132 KB Time limit exceeded
14 Correct 1 ms 2132 KB Output is correct
15 Execution timed out 1090 ms 2132 KB Time limit exceeded
16 Execution timed out 1088 ms 2132 KB Time limit exceeded
17 Execution timed out 1092 ms 2132 KB Time limit exceeded
18 Execution timed out 1083 ms 2132 KB Time limit exceeded
19 Execution timed out 1093 ms 2132 KB Time limit exceeded
20 Execution timed out 1093 ms 2132 KB Time limit exceeded
21 Execution timed out 1087 ms 2132 KB Time limit exceeded
22 Execution timed out 1094 ms 2128 KB Time limit exceeded
23 Execution timed out 1088 ms 2132 KB Time limit exceeded
24 Execution timed out 1092 ms 2132 KB Time limit exceeded
25 Execution timed out 1089 ms 2132 KB Time limit exceeded
26 Execution timed out 1079 ms 2128 KB Time limit exceeded
27 Execution timed out 1092 ms 2132 KB Time limit exceeded
28 Execution timed out 1084 ms 2132 KB Time limit exceeded
29 Execution timed out 1064 ms 2132 KB Time limit exceeded
30 Execution timed out 1086 ms 2132 KB Time limit exceeded
31 Execution timed out 1073 ms 2124 KB Time limit exceeded
32 Execution timed out 1080 ms 2132 KB Time limit exceeded
33 Execution timed out 1067 ms 2260 KB Time limit exceeded
34 Execution timed out 1073 ms 2260 KB Time limit exceeded
35 Incorrect 2 ms 2260 KB Output isn't correct
36 Execution timed out 1086 ms 2248 KB Time limit exceeded
37 Execution timed out 1070 ms 2260 KB Time limit exceeded
38 Incorrect 2 ms 2260 KB Output isn't correct
39 Execution timed out 1078 ms 2388 KB Time limit exceeded
40 Execution timed out 1089 ms 2388 KB Time limit exceeded
41 Incorrect 2 ms 2388 KB Output isn't correct
42 Execution timed out 1059 ms 2388 KB Time limit exceeded
43 Execution timed out 1069 ms 2388 KB Time limit exceeded
44 Incorrect 3 ms 2516 KB Output isn't correct
45 Execution timed out 1090 ms 2516 KB Time limit exceeded
46 Execution timed out 1083 ms 2516 KB Time limit exceeded
47 Incorrect 3 ms 2516 KB Output isn't correct
48 Execution timed out 1090 ms 2516 KB Time limit exceeded
49 Execution timed out 1088 ms 2516 KB Time limit exceeded
50 Incorrect 3 ms 2516 KB Output isn't correct
51 Execution timed out 1076 ms 2516 KB Time limit exceeded
52 Execution timed out 1043 ms 2644 KB Time limit exceeded
53 Incorrect 4 ms 2516 KB Output isn't correct
54 Execution timed out 1080 ms 2644 KB Time limit exceeded
55 Execution timed out 1084 ms 2644 KB Time limit exceeded
56 Incorrect 4 ms 2612 KB Output isn't correct
57 Execution timed out 1077 ms 2772 KB Time limit exceeded
58 Execution timed out 1083 ms 2772 KB Time limit exceeded
59 Incorrect 4 ms 2780 KB Output isn't correct
60 Execution timed out 1076 ms 2772 KB Time limit exceeded
61 Execution timed out 1077 ms 2856 KB Time limit exceeded
62 Incorrect 5 ms 2772 KB Output isn't correct
63 Incorrect 7 ms 2748 KB Output isn't correct
64 Incorrect 7 ms 2768 KB Output isn't correct
65 Incorrect 7 ms 2760 KB Output isn't correct
66 Incorrect 8 ms 2768 KB Output isn't correct
67 Correct 7 ms 2772 KB Output is correct
68 Incorrect 7 ms 2736 KB Output isn't correct
69 Incorrect 7 ms 2756 KB Output isn't correct
70 Incorrect 7 ms 2740 KB Output isn't correct
71 Incorrect 7 ms 2756 KB Output isn't correct
72 Incorrect 7 ms 2772 KB Output isn't correct
73 Incorrect 4 ms 2900 KB Output isn't correct
74 Incorrect 5 ms 2900 KB Output isn't correct
75 Incorrect 5 ms 2900 KB Output isn't correct
76 Incorrect 4 ms 2900 KB Output isn't correct
77 Incorrect 4 ms 2900 KB Output isn't correct
78 Correct 19 ms 3156 KB Output is correct
79 Execution timed out 1082 ms 3148 KB Time limit exceeded
80 Execution timed out 1079 ms 3184 KB Time limit exceeded
81 Execution timed out 1081 ms 3156 KB Time limit exceeded
82 Execution timed out 1076 ms 3212 KB Time limit exceeded
83 Incorrect 11 ms 3156 KB Output isn't correct
84 Incorrect 4 ms 2784 KB Output isn't correct
85 Incorrect 10 ms 3284 KB Output isn't correct
86 Incorrect 11 ms 3156 KB Output isn't correct
87 Incorrect 7 ms 3136 KB Output isn't correct
88 Incorrect 10 ms 3028 KB Output isn't correct
89 Incorrect 4 ms 2900 KB Output isn't correct
90 Incorrect 6 ms 3004 KB Output isn't correct
91 Incorrect 5 ms 3028 KB Output isn't correct
92 Incorrect 8 ms 3032 KB Output isn't correct