oj.uz

답안 #335497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
335497 2020-12-12T21:04:03 Z DavidDamian Mecho (IOI09_mecho) C++11
41 / 100
 213 ms 9552 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
char forest[805][805];
int n,s;
queue<pii> Q;
int timeBees[805][805];
int dx[4]={1,-1,0,0};
int dy[4]{0,0,1,-1};
void bfsBees(vector<pii> source){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            timeBees[i][j]=INT_MAX;
        }
    }
    for(pii u: source){
        timeBees[u.first][u.second]=0;
        Q.push(u);
    }
    while(!Q.empty()){
        pii u=Q.front();
        Q.pop();
        for(int mov=0;mov<4;mov++){
            int i=u.first+dx[mov];
            int j=u.second+dy[mov];
            if(i<1 || i>n) continue;
            if(j<1 || j>n) continue;
            if(forest[i][j]=='T' || forest[i][j]=='D') continue;
            if(timeBees[i][j]==INT_MAX){
                timeBees[i][j]=timeBees[u.first][u.second]+1;
                Q.push(pii(i,j));
            }
        }
    }
}
pii start;
pii goal;
int dist[805][805];
int fuel[805][805];
bool valid(int moment){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dist[i][j]=INT_MAX;
        }
    }
    dist[start.first][start.second]=moment;
    fuel[start.first][start.second]=0;
    Q.push(start);
    while(!Q.empty()){
        pii u=Q.front();
        Q.pop();
        for(int mov=0;mov<4;mov++){
            int i=u.first+dx[mov];
            int j=u.second+dy[mov];
            if(i<1 || i>n) continue;
            if(j<1 || j>n) continue;
            if(forest[i][j]=='T' || forest[i][j]=='H') continue;
            int nxt_dist=dist[u.first][u.second];
            if(fuel[u.first][u.second]==0)
                nxt_dist++;
            if(timeBees[i][j]<nxt_dist) continue;
            if(fuel[u.first][u.second]==1 && timeBees[i][j]==nxt_dist) continue;
            if(dist[i][j]==INT_MAX){
                dist[i][j]=nxt_dist;
                fuel[i][j]=(fuel[u.first][u.second]>0)? fuel[u.first][u.second]-1 : s-1;
                Q.push(pii(i,j));
            }
        }
    }
    return dist[goal.first][goal.second]!=INT_MAX;
}
int binarySearch(){
    int L=0,R=1600;
    int mid=(L+R)/2;
    int ans=-1;
    while(L<=R){
        mid=(L+R)/2;
        if(valid(mid)){
            ans=mid;
            L=mid+1;
        }
        else{
            R=mid-1;
        }
    }
    return ans;
}
int main()
{
    vector<pii> beeSource;
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>forest[i][j];
            if(forest[i][j]=='H'){
                beeSource.push_back(pii(i,j));
            }
            else if(forest[i][j]=='M'){
                start=pii(i,j);
            }
            else if(forest[i][j]=='D'){
                goal=pii(i,j);
            }
        }
    }
    bfsBees(beeSource);
    int last=binarySearch();
    cout<<last<<'\n';
    return 0;
}

Subtask #1
41.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 146 ms 8172 KB Output is correct
8 Incorrect 1 ms 620 KB Output isn't correct
9 Correct 1 ms 508 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Incorrect 1 ms 876 KB Output isn't correct
13 Incorrect 1 ms 892 KB Output isn't correct
14 Correct 1 ms 876 KB Output is correct
15 Incorrect 1 ms 492 KB Output isn't correct
16 Correct 1 ms 492 KB Output is correct
17 Incorrect 1 ms 492 KB Output isn't correct
18 Correct 1 ms 492 KB Output is correct
19 Incorrect 1 ms 492 KB Output isn't correct
20 Correct 1 ms 620 KB Output is correct
21 Incorrect 1 ms 640 KB Output isn't correct
22 Correct 1 ms 620 KB Output is correct
23 Incorrect 1 ms 748 KB Output isn't correct
24 Correct 1 ms 760 KB Output is correct
25 Incorrect 1 ms 896 KB Output isn't correct
26 Correct 1 ms 748 KB Output is correct
27 Incorrect 1 ms 876 KB Output isn't correct
28 Correct 1 ms 876 KB Output is correct
29 Incorrect 1 ms 876 KB Output isn't correct
30 Correct 1 ms 876 KB Output is correct
31 Incorrect 2 ms 1004 KB Output isn't correct
32 Correct 1 ms 1004 KB Output is correct
33 Incorrect 20 ms 3436 KB Output isn't correct
34 Incorrect 27 ms 4096 KB Output isn't correct
35 Correct 37 ms 4076 KB Output is correct
36 Incorrect 26 ms 3948 KB Output isn't correct
37 Incorrect 35 ms 4588 KB Output isn't correct
38 Correct 44 ms 4556 KB Output is correct
39 Incorrect 34 ms 4460 KB Output isn't correct
40 Incorrect 43 ms 5100 KB Output isn't correct
41 Correct 60 ms 5100 KB Output is correct
42 Incorrect 40 ms 4972 KB Output isn't correct
43 Incorrect 57 ms 5740 KB Output isn't correct
44 Correct 77 ms 5740 KB Output is correct
45 Incorrect 52 ms 5484 KB Output isn't correct
46 Incorrect 65 ms 6380 KB Output isn't correct
47 Correct 93 ms 6460 KB Output is correct
48 Incorrect 57 ms 5868 KB Output isn't correct
49 Incorrect 78 ms 6912 KB Output isn't correct
50 Correct 113 ms 6892 KB Output is correct
51 Incorrect 66 ms 6380 KB Output isn't correct
52 Incorrect 91 ms 7404 KB Output isn't correct
53 Correct 133 ms 7404 KB Output is correct
54 Incorrect 76 ms 6892 KB Output isn't correct
55 Incorrect 107 ms 8172 KB Output isn't correct
56 Correct 156 ms 8044 KB Output is correct
57 Incorrect 87 ms 7404 KB Output isn't correct
58 Incorrect 120 ms 8556 KB Output isn't correct
59 Correct 183 ms 8684 KB Output is correct
60 Incorrect 98 ms 8044 KB Output isn't correct
61 Incorrect 135 ms 9196 KB Output isn't correct
62 Correct 209 ms 9196 KB Output is correct
63 Correct 154 ms 9196 KB Output is correct
64 Correct 204 ms 9196 KB Output is correct
65 Correct 213 ms 9324 KB Output is correct
66 Correct 164 ms 9324 KB Output is correct
67 Correct 163 ms 9324 KB Output is correct
68 Correct 87 ms 9196 KB Output is correct
69 Correct 81 ms 9196 KB Output is correct
70 Correct 82 ms 9196 KB Output is correct
71 Correct 76 ms 9196 KB Output is correct
72 Incorrect 65 ms 7276 KB Output isn't correct
73 Incorrect 71 ms 9452 KB Output isn't correct
74 Correct 115 ms 9504 KB Output is correct
75 Correct 135 ms 9552 KB Output is correct
76 Correct 110 ms 9484 KB Output is correct
77 Correct 111 ms 9452 KB Output is correct
78 Correct 126 ms 8300 KB Output is correct
79 Correct 123 ms 7916 KB Output is correct
80 Correct 106 ms 8044 KB Output is correct
81 Correct 118 ms 8172 KB Output is correct
82 Correct 114 ms 7916 KB Output is correct
83 Correct 172 ms 8172 KB Output is correct
84 Correct 128 ms 8044 KB Output is correct
85 Correct 127 ms 8172 KB Output is correct
86 Correct 145 ms 8172 KB Output is correct
87 Correct 146 ms 8044 KB Output is correct
88 Correct 138 ms 8332 KB Output is correct
89 Correct 139 ms 8172 KB Output is correct
90 Correct 142 ms 8172 KB Output is correct
91 Correct 142 ms 8228 KB Output is correct
92 Correct 129 ms 8172 KB Output is correct