oj.uz

Submission #552765

# Submission time Handle Problem Language Result Execution time Memory
552765 2022-04-23T20:35:08 Z Iwanttobreakfree Mecho (IOI09_mecho) C++
19 / 100
 357 ms 43552 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfs(queue<int>& q,vector<int>& dist,vector<vector<int>>& g,int b){
    int n=dist.size();
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v:g[u]){
            if(dist[v]==-1&&v!=b){
                dist[v]=dist[u]+1;
                q.push(v);
            }
        }
    }
}
bool pos(int a,int b,int mid,int s,vector<vector<int>>& g,vector<int>& dist){
    int n=dist.size();
    vector<pair<int,int>> d(n,{-1,-1});
    queue<int> q;
    q.push(a);
    //cout<<mid<<'\n';
    if(mid>=dist[a])return false;
    d[a].first=mid;
    d[a].second=-1;
    while(!q.empty()){
        int u=q.front();
        if(u==b)return true;
        q.pop();
        //cout<<d[u].first<<' ';
        for(int v:g[u]){
            if(d[v].first==-1){
                d[v]=d[u];
                d[v].second++;
                if(d[v].second==s){
                    d[v].second=0;
                    d[v].first++;
                }
                if(d[v].first<dist[v])q.push(v);
            }
        }
    }
    return false;
}
int main(){
    int n,s,u,v;
    char c;
    cin>>n>>s;
    vector<vector<int>> g(n*n,vector<int>());
    vector<vector<char>> grid(n,vector<char>(n));
    vector<int> dist(n*n,-1);
    queue<int> q;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>grid[i][j];
            if(grid[i][j]=='T')continue;
            else{
                if(i&&grid[i-1][j]!='T'){
                    g[i*n+j].push_back(i*n+j-n);
                    g[i*n+j-n].push_back(i*n+j);
                }
                if(j&&grid[i][j-1]!='T'){
                    g[i*n+j].push_back(i*n+j-1);
                    g[i*n+j-1].push_back(i*n+j);
                }
                if(grid[i][j]=='D'){
                    v=i*n+j;
                    dist[v]=1e9;
                }
                if(grid[i][j]=='M')u=i*n+j;
                if(grid[i][j]=='H'){
                    q.push(i*n+j);
                    dist[i*n+j]=-1;
                }
            }
        }
    }
    bfs(q,dist,g,v);
    int l=0,r=1e9,ans=-1;
    while(l<=r){
        int mid=(r+l)/2;
        if(pos(u,v,mid,s,g,dist)){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    cout<<ans;
}

Compilation message

mecho.cpp: In function 'void bfs(std::queue<int>&, std::vector<int>&, std::vector<std::vector<int> >&, int)':
mecho.cpp:6:9: warning: unused variable 'n' [-Wunused-variable]
    6 |     int n=dist.size();
      |         ^
mecho.cpp: In function 'int main()':
mecho.cpp:48:10: warning: unused variable 'c' [-Wunused-variable]
   48 |     char c;
      |          ^
mecho.cpp:83:15: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |         if(pos(u,v,mid,s,g,dist)){
      |            ~~~^~~~~~~~~~~~~~~~~~
mecho.cpp:83:15: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
19.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Incorrect 302 ms 43552 KB Output isn't correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Incorrect 1 ms 468 KB Output isn't correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Incorrect 0 ms 212 KB Output isn't correct
17 Correct 0 ms 212 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Correct 1 ms 340 KB Output is correct
20 Incorrect 1 ms 340 KB Output isn't correct
21 Correct 1 ms 340 KB Output is correct
22 Incorrect 1 ms 340 KB Output isn't correct
23 Correct 1 ms 340 KB Output is correct
24 Incorrect 1 ms 340 KB Output isn't correct
25 Correct 1 ms 468 KB Output is correct
26 Incorrect 1 ms 468 KB Output isn't correct
27 Correct 1 ms 468 KB Output is correct
28 Incorrect 1 ms 468 KB Output isn't correct
29 Correct 1 ms 468 KB Output is correct
30 Incorrect 1 ms 468 KB Output isn't correct
31 Correct 1 ms 596 KB Output is correct
32 Incorrect 1 ms 596 KB Output isn't correct
33 Correct 18 ms 6676 KB Output is correct
34 Incorrect 17 ms 6660 KB Output isn't correct
35 Incorrect 48 ms 7576 KB Output isn't correct
36 Correct 26 ms 8616 KB Output is correct
37 Incorrect 23 ms 8592 KB Output isn't correct
38 Incorrect 66 ms 9832 KB Output isn't correct
39 Correct 28 ms 10768 KB Output is correct
40 Incorrect 31 ms 10828 KB Output isn't correct
41 Incorrect 89 ms 12328 KB Output isn't correct
42 Correct 37 ms 13308 KB Output is correct
43 Incorrect 35 ms 13260 KB Output isn't correct
44 Incorrect 118 ms 15216 KB Output isn't correct
45 Correct 43 ms 15972 KB Output is correct
46 Incorrect 43 ms 15984 KB Output isn't correct
47 Incorrect 142 ms 18288 KB Output isn't correct
48 Correct 52 ms 19148 KB Output is correct
49 Incorrect 51 ms 18960 KB Output isn't correct
50 Incorrect 168 ms 21772 KB Output isn't correct
51 Correct 61 ms 22192 KB Output is correct
52 Incorrect 60 ms 22228 KB Output isn't correct
53 Incorrect 202 ms 25432 KB Output isn't correct
54 Correct 70 ms 25764 KB Output is correct
55 Incorrect 69 ms 25624 KB Output isn't correct
56 Incorrect 243 ms 29552 KB Output isn't correct
57 Correct 92 ms 29484 KB Output is correct
58 Incorrect 93 ms 29516 KB Output isn't correct
59 Incorrect 285 ms 33868 KB Output isn't correct
60 Correct 93 ms 33520 KB Output is correct
61 Incorrect 92 ms 33432 KB Output isn't correct
62 Incorrect 357 ms 38564 KB Output isn't correct
63 Incorrect 218 ms 35432 KB Output isn't correct
64 Incorrect 320 ms 35384 KB Output isn't correct
65 Incorrect 330 ms 35512 KB Output isn't correct
66 Correct 258 ms 35416 KB Output is correct
67 Correct 241 ms 35508 KB Output is correct
68 Incorrect 158 ms 35368 KB Output isn't correct
69 Incorrect 166 ms 35408 KB Output isn't correct
70 Incorrect 164 ms 35468 KB Output isn't correct
71 Incorrect 155 ms 35468 KB Output isn't correct
72 Incorrect 153 ms 35404 KB Output isn't correct
73 Incorrect 213 ms 43448 KB Output isn't correct
74 Incorrect 249 ms 43488 KB Output isn't correct
75 Incorrect 259 ms 43452 KB Output isn't correct
76 Incorrect 244 ms 43444 KB Output isn't correct
77 Incorrect 253 ms 43456 KB Output isn't correct
78 Correct 262 ms 43452 KB Output is correct
79 Incorrect 222 ms 43488 KB Output isn't correct
80 Incorrect 231 ms 43440 KB Output isn't correct
81 Incorrect 231 ms 43472 KB Output isn't correct
82 Incorrect 221 ms 43368 KB Output isn't correct
83 Incorrect 291 ms 43380 KB Output isn't correct
84 Incorrect 273 ms 43520 KB Output isn't correct
85 Incorrect 279 ms 43400 KB Output isn't correct
86 Incorrect 301 ms 43380 KB Output isn't correct
87 Incorrect 265 ms 43404 KB Output isn't correct
88 Incorrect 286 ms 43420 KB Output isn't correct
89 Incorrect 303 ms 43552 KB Output isn't correct
90 Incorrect 303 ms 43340 KB Output isn't correct
91 Incorrect 292 ms 43428 KB Output isn't correct
92 Incorrect 296 ms 43420 KB Output isn't correct