oj.uz

Submission #1100014

# Submission time Handle Problem Language Result Execution time Memory
1100014 2024-10-12T11:33:47 Z asli_bg Mecho (IOI09_mecho) C++11
20 / 100
 1000 ms 18796 KB 
#pragma GCC optimize("O3,unroll-loops")

#include<bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define inset tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

//#define int long long

#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<pii> vii;

#define cont(x) for(auto el:x) {cout<<el<<' ';} cout<<endl;
//#define endl '\n'
#define contp(x) for(auto el:x) {cout<<el.fi<<'-'<<el.se<<' ';} cout<<endl;
#define pb push_back

#define sp <<' '<<

#define DEBUG(x) {cout<<(#x) sp x<<endl;}

const int MAXN=805;
const int INF=1e9;

int n,s;
vector<string> grid;
set<pii> ari;
int mark[MAXN][MAXN];

set<pii> hive;

pii bas,son;
int yon1[4]={1,-1,0,0};
int yon2[4]={0,0,-1,1};
//sag, sol, asagi, yukari

bool isvalid(int x,int y,bool f){
    if(x>=n or y>=n or x<0 or y<0) return false;
    if(f){
        if(grid[x][y]!='G') return false;
        if(hive.count({x,y})) return false;
    }
    else{
        if(grid[x][y]!='G' and grid[x][y]!='D') return false;
    }
    return true;
}

bool check(int deg){
    //düz shortest path bfs
    map<pii,bool> vis;
    queue<pair<pii,int>> q;
    q.push({bas,0});
    vis[bas]=true;

    //cout<<"DEEEEEG" sp deg<<endl;

    while(!q.empty()){
        auto el=q.front();
        q.pop();

        int adim=el.se;
        int x=el.fi.fi;
        int y=el.fi.se;
        //cout<<"control" sp adim sp x sp y<<endl;

        FOR(i,4){
            int yenix=x+yon1[i];
            int yeniy=y+yon2[i];

            if(!isvalid(yenix,yeniy,false)) continue;
            if(vis[{yenix,yeniy}]) continue;
            
            int sure=adim/s;
            //DEBUG(sure);
            //DEBUG(yenix);
            //DEBUG(yeniy);
            if(mark[yenix][yeniy]<deg+sure) continue;
            if((adim+1)%s==0){
                if(mark[yenix][yeniy]==deg+sure) continue;   
            }

            q.push({{yenix,yeniy},adim+1});
            vis[{yenix,yeniy}]=true;
        }
    }

    return vis[son];
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>s;
    grid.resize(n);
    FOR(i,n){
        cin>>grid[i];
    }

    FOR(i,n){
        FOR(j,n){
            if(grid[i][j]=='H'){
                hive.insert({i,j});
                mark[i][j]=0;
            }
            if(grid[i][j]=='M') {
                bas={i,j};
                mark[i][j]=INF;
            }
            if(grid[i][j]=='D'){
                son={i,j};
                mark[i][j]=INF;
            }
        }
    }

    for(int i=0;true;i++){ //x kez ilerle
        set<pii> tut;

        for(auto el:hive){
            FOR(i,4){
                int yenix=el.fi+yon1[i];
                int yeniy=el.se+yon2[i];
                if(isvalid(yenix,yeniy,true)){
                    tut.insert({yenix,yeniy});
                }
            }
        }

        if(tut.empty()) break;

        for(auto el:tut){
            mark[el.fi][el.se]=i+1;
            hive.insert(el);
        }
    }

    /*FOR(i,n){
        FOR(j,n) cout<<mark[i][j]<<' ';
        cout<<endl;
    }
    cout<<endl;*/


    int l=0;
    int r=n+1;
    while(l+1<r){
        int mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }

    cout<<l-1<<endl;
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Execution timed out 1101 ms 16920 KB Time limit exceeded
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Incorrect 33 ms 2732 KB Output isn't correct
13 Incorrect 10 ms 604 KB Output isn't correct
14 Correct 20 ms 2908 KB Output is correct
15 Incorrect 2 ms 344 KB Output isn't correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Incorrect 3 ms 348 KB Output isn't correct
18 Incorrect 2 ms 564 KB Output isn't correct
19 Incorrect 6 ms 348 KB Output isn't correct
20 Incorrect 3 ms 348 KB Output isn't correct
21 Incorrect 19 ms 572 KB Output isn't correct
22 Incorrect 10 ms 604 KB Output isn't correct
23 Incorrect 61 ms 644 KB Output isn't correct
24 Incorrect 30 ms 600 KB Output isn't correct
25 Incorrect 144 ms 2648 KB Output isn't correct
26 Incorrect 72 ms 2652 KB Output isn't correct
27 Incorrect 212 ms 2612 KB Output isn't correct
28 Incorrect 102 ms 2664 KB Output isn't correct
29 Incorrect 289 ms 2836 KB Output isn't correct
30 Incorrect 133 ms 2692 KB Output isn't correct
31 Incorrect 382 ms 2824 KB Output isn't correct
32 Incorrect 181 ms 2896 KB Output isn't correct
33 Execution timed out 1043 ms 2696 KB Time limit exceeded
34 Execution timed out 1030 ms 2940 KB Time limit exceeded
35 Execution timed out 1093 ms 5752 KB Time limit exceeded
36 Execution timed out 1047 ms 2896 KB Time limit exceeded
37 Execution timed out 1041 ms 2896 KB Time limit exceeded
38 Execution timed out 1067 ms 5716 KB Time limit exceeded
39 Execution timed out 1061 ms 2776 KB Time limit exceeded
40 Execution timed out 1069 ms 2916 KB Time limit exceeded
41 Execution timed out 1072 ms 5960 KB Time limit exceeded
42 Execution timed out 1066 ms 2900 KB Time limit exceeded
43 Execution timed out 1047 ms 2900 KB Time limit exceeded
44 Execution timed out 1050 ms 6024 KB Time limit exceeded
45 Execution timed out 1064 ms 2876 KB Time limit exceeded
46 Execution timed out 1016 ms 3152 KB Time limit exceeded
47 Execution timed out 1076 ms 6376 KB Time limit exceeded
48 Execution timed out 1049 ms 3020 KB Time limit exceeded
49 Execution timed out 1060 ms 3184 KB Time limit exceeded
50 Execution timed out 1055 ms 6396 KB Time limit exceeded
51 Execution timed out 1048 ms 3016 KB Time limit exceeded
52 Execution timed out 1066 ms 3064 KB Time limit exceeded
53 Execution timed out 1054 ms 6416 KB Time limit exceeded
54 Execution timed out 1096 ms 3152 KB Time limit exceeded
55 Execution timed out 1066 ms 3380 KB Time limit exceeded
56 Execution timed out 1070 ms 6484 KB Time limit exceeded
57 Execution timed out 1024 ms 1124 KB Time limit exceeded
58 Execution timed out 1047 ms 1384 KB Time limit exceeded
59 Execution timed out 1072 ms 6768 KB Time limit exceeded
60 Execution timed out 1101 ms 1364 KB Time limit exceeded
61 Execution timed out 1026 ms 1360 KB Time limit exceeded
62 Execution timed out 1057 ms 6864 KB Time limit exceeded
63 Execution timed out 1049 ms 5296 KB Time limit exceeded
64 Execution timed out 1032 ms 4604 KB Time limit exceeded
65 Execution timed out 1066 ms 4384 KB Time limit exceeded
66 Execution timed out 1072 ms 5264 KB Time limit exceeded
67 Execution timed out 1067 ms 4932 KB Time limit exceeded
68 Execution timed out 1071 ms 13040 KB Time limit exceeded
69 Execution timed out 1063 ms 12884 KB Time limit exceeded
70 Execution timed out 1073 ms 13144 KB Time limit exceeded
71 Execution timed out 1056 ms 13052 KB Time limit exceeded
72 Execution timed out 1048 ms 13140 KB Time limit exceeded
73 Execution timed out 1010 ms 18796 KB Time limit exceeded
74 Execution timed out 1038 ms 18772 KB Time limit exceeded
75 Execution timed out 1053 ms 18768 KB Time limit exceeded
76 Execution timed out 1058 ms 18772 KB Time limit exceeded
77 Execution timed out 1032 ms 18768 KB Time limit exceeded
78 Execution timed out 1061 ms 18260 KB Time limit exceeded
79 Execution timed out 1079 ms 18584 KB Time limit exceeded
80 Execution timed out 1075 ms 18516 KB Time limit exceeded
81 Execution timed out 1076 ms 18400 KB Time limit exceeded
82 Execution timed out 1040 ms 18516 KB Time limit exceeded
83 Execution timed out 1080 ms 18260 KB Time limit exceeded
84 Execution timed out 1071 ms 18540 KB Time limit exceeded
85 Execution timed out 1070 ms 18524 KB Time limit exceeded
86 Execution timed out 1043 ms 18516 KB Time limit exceeded
87 Execution timed out 1077 ms 18512 KB Time limit exceeded
88 Execution timed out 1043 ms 18256 KB Time limit exceeded
89 Execution timed out 1044 ms 18000 KB Time limit exceeded
90 Execution timed out 1063 ms 18004 KB Time limit exceeded
91 Execution timed out 1073 ms 18004 KB Time limit exceeded
92 Execution timed out 1016 ms 18000 KB Time limit exceeded