답안 #906799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
906799	2024-01-15T02:48:43 Z	Keshav211	Mecho (IOI09_mecho)	C++14	53 / 100	336 ms	41676 KB

mecho

#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

#	결과	실행 시간	메모리	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