oj.uz

Submission #624342

# Submission time Handle Problem Language Result Execution time Memory
624342 2022-08-08T02:01:22 Z jackkkk Mecho (IOI09_mecho) C++11
4 / 100
 219 ms 3336 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 = 10000;
    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 Incorrect 2 ms 2132 KB Output isn't correct
2 Incorrect 2 ms 2124 KB Output isn't correct
3 Incorrect 2 ms 2124 KB Output isn't correct
4 Incorrect 3 ms 2132 KB Output isn't correct
5 Incorrect 2 ms 2132 KB Output isn't correct
6 Incorrect 2 ms 2132 KB Output isn't correct
7 Incorrect 7 ms 2972 KB Output isn't correct
8 Incorrect 6 ms 2132 KB Output isn't correct
9 Incorrect 5 ms 2132 KB Output isn't correct
10 Incorrect 5 ms 2124 KB Output isn't correct
11 Incorrect 5 ms 2132 KB Output isn't correct
12 Incorrect 5 ms 2124 KB Output isn't correct
13 Incorrect 3 ms 2132 KB Output isn't correct
14 Correct 1 ms 2132 KB Output is correct
15 Incorrect 2 ms 2128 KB Output isn't correct
16 Incorrect 6 ms 2212 KB Output isn't correct
17 Incorrect 2 ms 2128 KB Output isn't correct
18 Incorrect 5 ms 2132 KB Output isn't correct
19 Incorrect 3 ms 2132 KB Output isn't correct
20 Incorrect 5 ms 2132 KB Output isn't correct
21 Incorrect 3 ms 2132 KB Output isn't correct
22 Incorrect 6 ms 2132 KB Output isn't correct
23 Incorrect 3 ms 2132 KB Output isn't correct
24 Incorrect 5 ms 2200 KB Output isn't correct
25 Incorrect 4 ms 2132 KB Output isn't correct
26 Incorrect 8 ms 2212 KB Output isn't correct
27 Incorrect 3 ms 2132 KB Output isn't correct
28 Incorrect 6 ms 2132 KB Output isn't correct
29 Incorrect 3 ms 2132 KB Output isn't correct
30 Incorrect 6 ms 2132 KB Output isn't correct
31 Incorrect 4 ms 2132 KB Output isn't correct
32 Incorrect 6 ms 2132 KB Output isn't correct
33 Incorrect 8 ms 2260 KB Output isn't correct
34 Incorrect 6 ms 2256 KB Output isn't correct
35 Incorrect 2 ms 2260 KB Output isn't correct
36 Incorrect 9 ms 2272 KB Output isn't correct
37 Incorrect 7 ms 2260 KB Output isn't correct
38 Incorrect 3 ms 2264 KB Output isn't correct
39 Incorrect 9 ms 2424 KB Output isn't correct
40 Incorrect 11 ms 2400 KB Output isn't correct
41 Incorrect 2 ms 2388 KB Output isn't correct
42 Incorrect 10 ms 2420 KB Output isn't correct
43 Incorrect 8 ms 2380 KB Output isn't correct
44 Incorrect 2 ms 2388 KB Output isn't correct
45 Incorrect 9 ms 2516 KB Output isn't correct
46 Incorrect 11 ms 2528 KB Output isn't correct
47 Incorrect 3 ms 2460 KB Output isn't correct
48 Incorrect 9 ms 2504 KB Output isn't correct
49 Incorrect 8 ms 2520 KB Output isn't correct
50 Incorrect 3 ms 2520 KB Output isn't correct
51 Incorrect 10 ms 2624 KB Output isn't correct
52 Incorrect 10 ms 2648 KB Output isn't correct
53 Incorrect 4 ms 2648 KB Output isn't correct
54 Incorrect 10 ms 2652 KB Output isn't correct
55 Incorrect 10 ms 2652 KB Output isn't correct
56 Incorrect 4 ms 2648 KB Output isn't correct
57 Incorrect 11 ms 2776 KB Output isn't correct
58 Incorrect 12 ms 2792 KB Output isn't correct
59 Incorrect 5 ms 2776 KB Output isn't correct
60 Incorrect 11 ms 2756 KB Output isn't correct
61 Incorrect 10 ms 2872 KB Output isn't correct
62 Incorrect 5 ms 2772 KB Output isn't correct
63 Incorrect 7 ms 2800 KB Output isn't correct
64 Incorrect 7 ms 2752 KB Output isn't correct
65 Incorrect 7 ms 2772 KB Output isn't correct
66 Incorrect 7 ms 2772 KB Output isn't correct
67 Correct 7 ms 2772 KB Output is correct
68 Incorrect 7 ms 2868 KB Output isn't correct
69 Incorrect 7 ms 2776 KB Output isn't correct
70 Incorrect 9 ms 2776 KB Output isn't correct
71 Incorrect 8 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 4 ms 2904 KB Output isn't correct
75 Incorrect 5 ms 2900 KB Output isn't correct
76 Incorrect 4 ms 2904 KB Output isn't correct
77 Incorrect 4 ms 2888 KB Output isn't correct
78 Correct 20 ms 3156 KB Output is correct
79 Incorrect 189 ms 3336 KB Output isn't correct
80 Incorrect 210 ms 3300 KB Output isn't correct
81 Incorrect 219 ms 3204 KB Output isn't correct
82 Incorrect 201 ms 3284 KB Output isn't correct
83 Incorrect 14 ms 3156 KB Output isn't correct
84 Incorrect 5 ms 2772 KB Output isn't correct
85 Incorrect 11 ms 3156 KB Output isn't correct
86 Incorrect 11 ms 3156 KB Output isn't correct
87 Incorrect 7 ms 3164 KB Output isn't correct
88 Incorrect 10 ms 3096 KB Output isn't correct
89 Incorrect 5 ms 2900 KB Output isn't correct
90 Incorrect 6 ms 3028 KB Output isn't correct
91 Incorrect 5 ms 3028 KB Output isn't correct
92 Incorrect 8 ms 3028 KB Output isn't correct