oj.uz

Submission #1119585

# Submission time Handle Problem Language Result Execution time Memory
1119585 2024-11-27T07:00:10 Z sktodow Mecho (IOI09_mecho) C++17
9 / 100
 204 ms 8276 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
// #define int long long int
#define pb push_back
#define mid (l+(r-l)/2)
#define f first
#define s second
static const int N=805;
static const long long int MOD=(1LL<<61)-1;
static const long long int inf=INT64_MAX;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
 
void io(string name = ""){ 
    freopen((name+".in").c_str(), "r", stdin);
    freopen((name+".out").c_str(), "w", stdout);
}

int n,x,mx,my;
vector<vector<char>>v(N,vector<char>(N));
vector<vector<int>>bee(N,vector<int>(N,-1));
int mec[N][N];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};

bool inside(int a,int b){return ((a<=n && a>0)&&(b<=n && b>0)&&v[a][b]!='T');}

void calcbee(){
    queue<array<int,3>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(v[i][j]=='H'){q.push({i,j,0});}
        }
    }
    while(q.size()){
        array<int,3>curr=q.front();
        q.pop();
        if(bee[curr[0]][curr[1]]!=-1){continue;}
        bee[curr[0]][curr[1]]=curr[2];
        for(int i=0;i<4;i++){
            if(inside(curr[0]+dx[i],curr[1]+dy[i])){
                q.push({curr[0]+dx[i],curr[1]+dy[i],curr[2]+1});
            }
        }
    }
}

bool mecho(int k){
    queue<array<int,3>>q;
    q.push({mx,my,k});
    while(q.size()){
        array<int,3>curr=q.front();
        q.pop();
        if(mec[curr[0]][curr[1]]!=-1){continue;}
        
        mec[curr[0]][curr[1]]=curr[2];
        if(v[curr[0]][curr[1]]=='D'){return 1;}
        for(int i=0;i<4;i++){
            if(inside(curr[0]+dx[i],curr[1]+dy[i]) && bee[curr[0]+dx[i]][curr[1]+dy[i]]>=(curr[2]+1)/x){
                q.push({curr[0]+dx[i],curr[1]+dy[i],curr[2]+1});
            }
        }
    }
    return 0;
}

int32_t main(){
    //io("local");
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>v[i][j];
            if(v[i][j]=='M'){mx=i,my=j;}
        }
    }
    calcbee();
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=n;j++){cout<<bee[i][j]<<" ";}
    //     cout<<endl;
    // }
    int l=0,r=bee[mx][my];
    bool chc=0,achc=0;
    while(l<r-1){
        memset(mec,-1,sizeof(mec));
        chc=mecho(mid*(x+1));
        // cout<<mid<<" "<<chc<<endl;
        if(chc){l=mid;achc=1;}
        else{r=mid;}
        
        // for(int i=1;i<=n;i++){
        //     for(int j=1;j<=n;j++){cout<<mec[i][j]<<" ";}
        //     cout<<endl;
        // }
        // cout<<endl;
    }
    if(!achc){cout<<-1;}
    else{cout<<l;}
    return 0;
}

Compilation message

mecho.cpp: In function 'void io(std::string)':
mecho.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen((name+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((name+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6228 KB Output is correct
2 Incorrect 7 ms 6228 KB Output isn't correct
3 Incorrect 5 ms 6228 KB Output isn't correct
4 Incorrect 6 ms 6228 KB Output isn't correct
5 Incorrect 5 ms 6228 KB Output isn't correct
6 Incorrect 6 ms 6228 KB Output isn't correct
7 Correct 148 ms 7344 KB Output is correct
8 Correct 7 ms 6228 KB Output is correct
9 Correct 5 ms 6000 KB Output is correct
10 Incorrect 6 ms 6228 KB Output isn't correct
11 Correct 5 ms 6228 KB Output is correct
12 Incorrect 6 ms 6228 KB Output isn't correct
13 Incorrect 4 ms 3836 KB Output isn't correct
14 Correct 7 ms 6028 KB Output is correct
15 Incorrect 6 ms 6228 KB Output isn't correct
16 Incorrect 6 ms 6228 KB Output isn't correct
17 Incorrect 7 ms 6072 KB Output isn't correct
18 Incorrect 6 ms 6228 KB Output isn't correct
19 Incorrect 6 ms 6404 KB Output isn't correct
20 Incorrect 6 ms 6228 KB Output isn't correct
21 Incorrect 6 ms 6228 KB Output isn't correct
22 Incorrect 7 ms 6228 KB Output isn't correct
23 Incorrect 7 ms 6228 KB Output isn't correct
24 Incorrect 7 ms 6228 KB Output isn't correct
25 Incorrect 7 ms 6316 KB Output isn't correct
26 Incorrect 7 ms 6228 KB Output isn't correct
27 Incorrect 6 ms 6228 KB Output isn't correct
28 Incorrect 7 ms 6228 KB Output isn't correct
29 Incorrect 6 ms 6392 KB Output isn't correct
30 Incorrect 6 ms 6228 KB Output isn't correct
31 Incorrect 7 ms 6228 KB Output isn't correct
32 Incorrect 6 ms 6228 KB Output isn't correct
33 Incorrect 12 ms 6228 KB Output isn't correct
34 Incorrect 9 ms 6232 KB Output isn't correct
35 Incorrect 39 ms 6228 KB Output isn't correct
36 Incorrect 13 ms 6376 KB Output isn't correct
37 Incorrect 13 ms 6228 KB Output isn't correct
38 Incorrect 56 ms 6228 KB Output isn't correct
39 Incorrect 14 ms 6272 KB Output isn't correct
40 Incorrect 11 ms 6440 KB Output isn't correct
41 Incorrect 60 ms 6452 KB Output isn't correct
42 Incorrect 13 ms 6484 KB Output isn't correct
43 Incorrect 15 ms 6228 KB Output isn't correct
44 Incorrect 74 ms 6492 KB Output isn't correct
45 Incorrect 17 ms 6484 KB Output isn't correct
46 Incorrect 14 ms 6484 KB Output isn't correct
47 Incorrect 82 ms 6340 KB Output isn't correct
48 Incorrect 14 ms 6368 KB Output isn't correct
49 Incorrect 16 ms 6364 KB Output isn't correct
50 Incorrect 125 ms 6484 KB Output isn't correct
51 Incorrect 17 ms 6500 KB Output isn't correct
52 Incorrect 19 ms 6484 KB Output isn't correct
53 Incorrect 146 ms 6484 KB Output isn't correct
54 Incorrect 19 ms 6484 KB Output isn't correct
55 Incorrect 18 ms 6484 KB Output isn't correct
56 Incorrect 182 ms 6732 KB Output isn't correct
57 Incorrect 19 ms 6740 KB Output isn't correct
58 Incorrect 20 ms 6784 KB Output isn't correct
59 Incorrect 191 ms 6736 KB Output isn't correct
60 Incorrect 20 ms 6740 KB Output isn't correct
61 Incorrect 22 ms 6752 KB Output isn't correct
62 Incorrect 204 ms 6880 KB Output isn't correct
63 Incorrect 91 ms 6732 KB Output isn't correct
64 Correct 184 ms 6640 KB Output is correct
65 Incorrect 149 ms 6748 KB Output isn't correct
66 Incorrect 143 ms 6740 KB Output isn't correct
67 Correct 113 ms 6636 KB Output is correct
68 Incorrect 55 ms 6740 KB Output isn't correct
69 Correct 45 ms 6740 KB Output is correct
70 Correct 44 ms 6756 KB Output is correct
71 Correct 42 ms 6732 KB Output is correct
72 Correct 36 ms 6732 KB Output is correct
73 Correct 60 ms 8268 KB Output is correct
74 Correct 134 ms 8276 KB Output is correct
75 Incorrect 135 ms 8264 KB Output isn't correct
76 Incorrect 126 ms 8268 KB Output isn't correct
77 Incorrect 129 ms 8264 KB Output isn't correct
78 Correct 128 ms 7964 KB Output is correct
79 Correct 123 ms 7976 KB Output is correct
80 Incorrect 139 ms 7992 KB Output isn't correct
81 Incorrect 143 ms 8268 KB Output isn't correct
82 Incorrect 95 ms 8268 KB Output isn't correct
83 Incorrect 145 ms 8044 KB Output isn't correct
84 Correct 131 ms 7848 KB Output is correct
85 Incorrect 153 ms 8012 KB Output isn't correct
86 Incorrect 170 ms 7840 KB Output isn't correct
87 Incorrect 170 ms 8012 KB Output isn't correct
88 Incorrect 153 ms 7760 KB Output isn't correct
89 Correct 179 ms 7756 KB Output is correct
90 Correct 169 ms 7756 KB Output is correct
91 Correct 168 ms 7756 KB Output is correct
92 Incorrect 158 ms 7756 KB Output isn't correct