oj.uz

Submission #906799

# Submission time Handle Problem Language Result Execution time Memory
906799 2024-01-15T02:48:43 Z Keshav211 Mecho (IOI09_mecho) C++14
53 / 100
 336 ms 41676 KB 
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <chrono>
#include <string>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <climits>
#include <bitset>
#define all(x) (x).begin(), (x).end()
#define vec(n) vll arr(n);
#define printarr(arr) for(auto i:arr)cout<<i<<" "; cout<<endl;
#define printdict(dict) for(auto i:dict)cout<<i.first<<": "<<i.second<<endl;
#define printadj(adj) for(ll i=0;i<n;i++){if(!adj[i].empty()){cout<<i<<": ";printarr(adj[i])}}
#define read(arr); for(ll i=0;i<arr.size();i++) cin>>arr[i];
#define readundirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);adj[b].pb(a);}
#define readdirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);}
#define readfunc(n) for(ll i=0;i<n;i++){ll a;cin>>a;a--;func_adj[i]=a;}
#define grid(n,m) for (ll i=1;i<=n;i++){for (ll j=1;j<=m;j++) cin>>graph[i][j];}
#define vll vector<ll>
#define sll set<ll>
#define msll multiset<ll>
#define qll queue<ll>
#define pll pair<ll,ll>
#define str string
#define pb push_back
#define ll long long
#define ld long double
using namespace std;
const str alph="abcdefghijklmnopqrstuvwxyz";
const str capalph="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll inf=2e5+1;
const ll graph_size=1000;
const ll mod=1e9+7;
const ll large=1e18;
const ll small=-1e18;
// Fast Input/Output
void fastio(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
}
// File Input/Output
str fileio(const string&filePath=__FILE__){
    size_t lastSlash=filePath.find_last_of('/');
    size_t lastDot=filePath.rfind('.');
    return filePath.substr(lastSlash+1,lastDot-lastSlash-1);
}
// For Yes Or No Problems
str yes_or_no(bool test){
    if (test){
       return "YES";
    }
    return "NO";
}
ll n,m,q,s;
// Floodfill
char graph[graph_size+2][graph_size+2];
vector<pll> directions={{0,-1},{-1,0},{1,0},{0,1}};
bool floodfill_visited[graph_size+2][graph_size+2];
ll floodfill_bear_level[graph_size+2][graph_size+2];
pll floodfill_parent[graph_size+2][graph_size+2];
void floodfill_bear_bfs(pll coord){
    for (ll i=0;i<=n+1;i++){
        for (ll j=0;j<=m+1;j++){
            floodfill_bear_level[i][j]=large;
            floodfill_parent[i][j]={-1,-1};
            floodfill_visited[i][j]=0;
        }
    }
    ll x=coord.first;
    ll y=coord.second;
    queue<pll> q;
    q.push({x,y});
    floodfill_bear_level[x][y]=0;
    while (!q.empty()){
        pll curr=q.front();
        q.pop();
        x=curr.first;
        y=curr.second;
        floodfill_visited[x][y]=1;
        for (auto i:directions){
            if (graph[x+i.first][y+i.second]!='T' and x+i.first>=1 and x+i.first<=n and y+i.second>=1 and y+i.second<=m and floodfill_bear_level[x+i.first][y+i.second]==large){
                floodfill_bear_level[x+i.first][y+i.second]=floodfill_bear_level[x][y]+1;
                floodfill_parent[x+i.first][y+i.second]={x,y};
                q.push({x+i.first,y+i.second});
            }
        }
    }
}
ll floodfill_bee_level[graph_size+2][graph_size+2];
vector<pll> hives;
void floodfill_bee_bfs(){
    for (ll i=0;i<=n+1;i++){
        for (ll j=0;j<=m+1;j++){
            floodfill_bee_level[i][j]=large;
            floodfill_parent[i][j]={-1,-1};
            floodfill_visited[i][j]=0;
        }
    }
    queue<pll> q;
    for (auto i:hives){
        q.push(i);
        floodfill_bee_level[i.first][i.second]=0;
    }
    while (!q.empty()){
        pll curr=q.front();
        q.pop();
        ll x=curr.first;
        ll y=curr.second;
        floodfill_visited[x][y]=1;
        for (auto i:directions){
            if (graph[x+i.first][y+i.second]!='T' and x+i.first>=1 and x+i.first<=n and y+i.second>=1 and y+i.second<=m and floodfill_bee_level[x+i.first][y+i.second]==large){
                floodfill_bee_level[x+i.first][y+i.second]=floodfill_bee_level[x][y]+1;
                floodfill_parent[x+i.first][y+i.second]={x,y};
                q.push({x+i.first,y+i.second});
            }
        }
    }
}
bool graph1[graph_size+2][graph_size+2];
ll floodfill_ans_level[graph_size+2][graph_size+2];
void floodfill_ans_bfs(pll coord,ll t){
    for (ll i=0;i<=n+1;i++){
        for (ll j=0;j<=m+1;j++){
            floodfill_ans_level[i][j]=large;
            floodfill_parent[i][j]={-1,-1};
            floodfill_visited[i][j]=0;
        }
    }
    ll x=coord.first;
    ll y=coord.second;
    queue<pll> q;
    q.push({x,y});
    floodfill_ans_level[x][y]=0;
    while (!q.empty()){
        pll curr=q.front();
        q.pop();
        x=curr.first;
        y=curr.second;
        floodfill_visited[x][y]=1;
        for (auto i:directions){
            if (graph[x+i.first][y+i.second]!='T' and (floodfill_ans_level[x][y]+1)/s+t<floodfill_bee_level[x+i.first][y+i.second] and x+i.first>=1 and x+i.first<=n and y+i.second>=1 and y+i.second<=m and floodfill_ans_level[x+i.first][y+i.second]==large){
                floodfill_ans_level[x+i.first][y+i.second]=floodfill_ans_level[x][y]+1;
                floodfill_parent[x+i.first][y+i.second]={x,y};
                q.push({x+i.first,y+i.second});
            }
        }
    }
}
// Binary Search
pll home,bear;
bool check(ll t){
    if (t>=floodfill_bee_level[bear.first][bear.second]){
        return 0;
    }
    floodfill_ans_bfs(bear,t);
    bool test=0;
    for (auto i:directions){
        test=max(test,floodfill_visited[home.first+i.first][home.second+i.second]);
    }
    return test;
}
// Returns the first value in the range such that check(value)=True.
ll first_true(ll low,ll high){
    while (low<high){
        ll mid=(low+high)/2;
        if (check(mid)){
            high=mid;
        }
        else{
            low=mid+1;
        }
    }
    return low;
}
// Returns the last value in the range such that check(value)=True.
ll last_true(ll low,ll high){
    while (low<high){
        ll mid=(low+high+1)/2;
        if (check(mid)){
            low=mid;
        }
        else{
            high=mid-1;
        }
    }
    return low;
}
int main(){
    // auto start_time=chrono::steady_clock::now();
    fastio();
    // str filename=fileio();
    // ifstream cin(filename+".in");
    // ofstream cout(filename+".out");
    ll t=1;
    // cin>>t;
    while (t--){
        cin>>n>>s;
        m=n;
        grid(n,m);
        for (ll i=1;i<=n;i++){
            for (ll j=1;j<=m;j++){
                if (graph[i][j]=='H'){
                    hives.pb({i,j});
                }
                if (graph[i][j]=='M'){
                    bear={i,j};
                }
                if (graph[i][j]=='D'){
                    home={i,j};
                }
            }
        }
        floodfill_bear_bfs(bear);
        floodfill_bee_bfs();
        // for (ll i=0;i<=n+1;i++){
        //     for (ll j=0;j<=m+1;j++){
        //         if (floodfill_bear_level[i][j]!=large){
        //             // ld val=floodfill_bear_level[i][j];
        //             // val/=s;
        //             // floodfill_bear_level[i][j]=ceil(val);
        //             floodfill_bear_level[i][j]/=s;
        //         }
        //     }
        // }
        // for (ll i=1;i<=n;i++){
        //     for (ll j=1;j<=m;j++){
        //         if (floodfill_bear_level[i][j]==large) cout<<-1<<" ";
        //         else cout<<floodfill_bear_level[i][j]<<" ";
        //     }
        //     cout<<"\n";
        // }
        // cout<<"\n";
        // for (ll i=1;i<=n;i++){
        //     for (ll j=1;j<=m;j++){
        //         if (floodfill_bee_level[i][j]==large) cout<<-1<<" ";
        //         else cout<<floodfill_bee_level[i][j]<<" ";
        //     }
        //     cout<<"\n";
        // }
        // cout<<"\n";
        ll ans=last_true(0,n+m);
        if (!check(0)){
            ans--;
        }
        cout<<ans<<"\n";
    }
    // auto end_time=chrono::steady_clock::now();
    // auto elapsed_time=chrono::duration_cast<chrono::milliseconds>(end_time-start_time);
    // cout<<"Elapsed time: "<<elapsed_time.count()<<" milliseconds\n";
}

Subtask #1
53.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8656 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8672 KB Output is correct
7 Correct 247 ms 41112 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8536 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Incorrect 3 ms 10844 KB Output isn't correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Incorrect 2 ms 8540 KB Output isn't correct
16 Incorrect 2 ms 8540 KB Output isn't correct
17 Incorrect 2 ms 10844 KB Output isn't correct
18 Incorrect 2 ms 10844 KB Output isn't correct
19 Incorrect 3 ms 10844 KB Output isn't correct
20 Incorrect 2 ms 10844 KB Output isn't correct
21 Incorrect 2 ms 10752 KB Output isn't correct
22 Incorrect 3 ms 10844 KB Output isn't correct
23 Incorrect 3 ms 10844 KB Output isn't correct
24 Incorrect 2 ms 10840 KB Output isn't correct
25 Incorrect 2 ms 10844 KB Output isn't correct
26 Incorrect 2 ms 10840 KB Output isn't correct
27 Incorrect 3 ms 10844 KB Output isn't correct
28 Incorrect 3 ms 10844 KB Output isn't correct
29 Incorrect 3 ms 10844 KB Output isn't correct
30 Incorrect 3 ms 10712 KB Output isn't correct
31 Incorrect 3 ms 12892 KB Output isn't correct
32 Incorrect 3 ms 12892 KB Output isn't correct
33 Incorrect 17 ms 23644 KB Output isn't correct
34 Incorrect 20 ms 23644 KB Output isn't correct
35 Correct 25 ms 23644 KB Output is correct
36 Incorrect 21 ms 25688 KB Output isn't correct
37 Incorrect 23 ms 25688 KB Output isn't correct
38 Correct 32 ms 25876 KB Output is correct
39 Incorrect 25 ms 25692 KB Output isn't correct
40 Incorrect 27 ms 25692 KB Output isn't correct
41 Correct 40 ms 25692 KB Output is correct
42 Incorrect 34 ms 28240 KB Output isn't correct
43 Incorrect 35 ms 27868 KB Output isn't correct
44 Correct 49 ms 28044 KB Output is correct
45 Incorrect 43 ms 32092 KB Output isn't correct
46 Incorrect 47 ms 32092 KB Output isn't correct
47 Correct 78 ms 32080 KB Output is correct
48 Incorrect 46 ms 34384 KB Output isn't correct
49 Incorrect 54 ms 34384 KB Output isn't correct
50 Correct 90 ms 34384 KB Output is correct
51 Incorrect 57 ms 36444 KB Output isn't correct
52 Incorrect 66 ms 36548 KB Output isn't correct
53 Correct 178 ms 36564 KB Output is correct
54 Incorrect 68 ms 36664 KB Output isn't correct
55 Incorrect 82 ms 36660 KB Output isn't correct
56 Correct 198 ms 36684 KB Output is correct
57 Incorrect 81 ms 38556 KB Output isn't correct
58 Incorrect 97 ms 38736 KB Output isn't correct
59 Correct 248 ms 38860 KB Output is correct
60 Incorrect 95 ms 40896 KB Output isn't correct
61 Incorrect 104 ms 40900 KB Output isn't correct
62 Correct 336 ms 40840 KB Output is correct
63 Correct 172 ms 41036 KB Output is correct
64 Correct 237 ms 40788 KB Output is correct
65 Correct 219 ms 40736 KB Output is correct
66 Correct 199 ms 40916 KB Output is correct
67 Correct 164 ms 40788 KB Output is correct
68 Correct 94 ms 40792 KB Output is correct
69 Correct 99 ms 40784 KB Output is correct
70 Correct 101 ms 40984 KB Output is correct
71 Correct 93 ms 40784 KB Output is correct
72 Correct 76 ms 40788 KB Output is correct
73 Correct 104 ms 41612 KB Output is correct
74 Correct 174 ms 41504 KB Output is correct
75 Correct 178 ms 41444 KB Output is correct
76 Correct 147 ms 41556 KB Output is correct
77 Correct 171 ms 41360 KB Output is correct
78 Correct 165 ms 41556 KB Output is correct
79 Correct 156 ms 41360 KB Output is correct
80 Correct 154 ms 41496 KB Output is correct
81 Correct 162 ms 41556 KB Output is correct
82 Correct 159 ms 41556 KB Output is correct
83 Correct 233 ms 41296 KB Output is correct
84 Correct 255 ms 41676 KB Output is correct
85 Correct 255 ms 41296 KB Output is correct
86 Correct 247 ms 41476 KB Output is correct
87 Correct 222 ms 41300 KB Output is correct
88 Correct 231 ms 41360 KB Output is correct
89 Correct 288 ms 41364 KB Output is correct
90 Correct 284 ms 41296 KB Output is correct
91 Correct 289 ms 41364 KB Output is correct
92 Correct 272 ms 41364 KB Output is correct