oj.uz

Submission #986148

# Submission time Handle Problem Language Result Execution time Memory
986148 2024-05-19T22:22:52 Z sarthakgangwal Mecho (IOI09_mecho) C++14
4 / 100
 174 ms 25944 KB 
//This code is written by sarthakgangwal
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define tc int t;cin>>t;while(t--)
#define el "/n"
#define sp ' '
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define vvpll vector<vector<pair<long long int, long long int>>>
#define vpll vector<pair<long long int,long long int>>
#define vb vector<bool>
#define pb push_back
#define pll pair<long long int,long long int>
#define ff first
#define ss second
#define I(x) ll x;cin>>x
#define CC(x) cout << (x) << endl
#define mod 1000000007
#define PI 3.14159265
long long INF = 2e18;
#define vll_in(v,n) for(ll i=0;i<=n-1;i++){ ll x;cin>>x; v.push_back(x);}
#define vvll_in(mat,r,c) for(ll i=0;i<=r-1;i++){ vector<ll> v;for(ll j=0;j<=c-1;j++){ll x;cin>>x;v.push_back(x);};mat.push_back(v);}
void print(bool k){cout << (k ? "YES" : "NO") <<"\n";}
void print(vll k,string sep = " ",string endline = "\n") {for (ll &i : k) cout << i << sep; cout << endline;}
#define all(x) (x).begin(), (x).end()

/*-------------------------------------Imp Concepts---------------------------------------------->
48-57 -> 0-9
65-90 -> A-Z
97-122 -> a-z
(a +-* b) mod M = ((a mod M) +-* (b mod M)) mod M.

use ordered set using oset<ll> , 2 extra functions
.order_of_key(k) gives number of items strictly smaller than k
.find_by_order(k) gives iterator to kth element in set 0 indexing
rest all functionalities are same as stl set like lowerbound upperbound erase find etc

use ordered multiset using oset<pll>
search upper_bound({val,-1})
insert insert({val,index}) index used so same val can be inserted uniquely
delete .erase( .upper_bound({val,-1}))
-----------------------------CODE BEGIN :)-----------------------------------------*/
ll forest[802][802];
vector<vector<pll>> M_ini(802,vpll(802,{INF,INF}));
vector<vector<pll>> M;

ll mx,my;
ll dx,dy;
vpll bees;
ll n,s;

ll movy[4] = {-1,0,1,0};
ll movx[4] = {0,1,0,-1};
bool ok=0;
void bfs1(){
    queue<pll> q;
    for(pll p:bees){q.push(p);}

    while(!q.empty()){
        pll top = q.front();q.pop();
        ll x =top.ff, y=top.ss;
        for(int i=0;i<4;i++){
            ll xx=x+movx[i],yy=y+movy[i];
            if(forest[xx][yy]==-1){
                forest[xx][yy]=1+forest[x][y];
                q.push({xx,yy});
            }
        }
    }
    return;
}

bool bfs2(ll st){
    M=M_ini;
    if(forest[mx][my]<=st){return 0;}
    queue<pll> q;
    q.push({mx,my});
    M[mx][my]={st,0};
    while(!q.empty()){
        pll top = q.front();q.pop();
        ll x =top.ff, y=top.ss;
        ll tim=M[x][y].ff, stp=M[x][y].ss;
        for(int i=0;i<4;i++){
            ll xx=x+movx[i],yy=y+movy[i];
            if(xx==dx && yy==dy){ok=1;return 1;}
            if(M[xx][yy].ff==INF && forest[xx][yy]!=-2){
                if(stp<s-1){M[xx][yy]={tim,stp+1};}
                else{M[xx][yy]={tim+1,0};}

                if(M[xx][yy].ff<=forest[xx][yy]){
                    q.push({xx,yy});
                }
                else{
                    M[xx][yy].ff=INF;M[xx][yy].ss=INF;
                }
            }
        }
    }
    return 0;
}

int main(){
    fast
    {
        cin>>n>>s;
        char x;
        for(ll i=0;i<802;i++){
            forest[0][i]=-2;
            forest[n+1][i]=-2;
            forest[801][i]=-2;
            forest[i][0]=-2;
            forest[i][n+1]=-2;
            forest[i][801]=-2;
        }
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=n;j++){
                cin>>x;
                if(x=='M'){mx=i;my=j;forest[i][j]=-1;}
                if(x=='G'){forest[i][j]=-1;}
                if(x=='H'){forest[i][j]=0;bees.pb({i,j});}
                if(x=='T'){forest[i][j]=-2;}
                if(x=='D'){forest[i][j]=-1;dx=i;dy=j;}
            }
        }

        bfs1();
        
        ll l=0,h=forest[dx][dy]+1;
        while(l<h){
            ll m = (l+h)/2;
            if(m==l){if(bfs2(h)){l=h;}break;}
            if(bfs2(m)){l=m;}
            else{h=m-1;}
        }
        if(!ok){CC(-1);}
        else{CC(l);}

    }
}

Subtask #1
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 25180 KB Output isn't correct
2 Incorrect 10 ms 25368 KB Output isn't correct
3 Incorrect 12 ms 25180 KB Output isn't correct
4 Incorrect 12 ms 25176 KB Output isn't correct
5 Incorrect 12 ms 25180 KB Output isn't correct
6 Incorrect 11 ms 25180 KB Output isn't correct
7 Incorrect 56 ms 25936 KB Output isn't correct
8 Correct 11 ms 25180 KB Output is correct
9 Correct 12 ms 25180 KB Output is correct
10 Incorrect 13 ms 25400 KB Output isn't correct
11 Incorrect 11 ms 25400 KB Output isn't correct
12 Incorrect 10 ms 25436 KB Output isn't correct
13 Incorrect 12 ms 25436 KB Output isn't correct
14 Correct 11 ms 25436 KB Output is correct
15 Incorrect 15 ms 25180 KB Output isn't correct
16 Incorrect 14 ms 25180 KB Output isn't correct
17 Incorrect 16 ms 25300 KB Output isn't correct
18 Incorrect 15 ms 25176 KB Output isn't correct
19 Incorrect 17 ms 25528 KB Output isn't correct
20 Incorrect 16 ms 25492 KB Output isn't correct
21 Incorrect 17 ms 25180 KB Output isn't correct
22 Incorrect 16 ms 25180 KB Output isn't correct
23 Incorrect 18 ms 25436 KB Output isn't correct
24 Incorrect 16 ms 25436 KB Output isn't correct
25 Incorrect 20 ms 25436 KB Output isn't correct
26 Incorrect 19 ms 25236 KB Output isn't correct
27 Incorrect 20 ms 25436 KB Output isn't correct
28 Incorrect 18 ms 25352 KB Output isn't correct
29 Incorrect 20 ms 25432 KB Output isn't correct
30 Incorrect 17 ms 25436 KB Output isn't correct
31 Incorrect 20 ms 25688 KB Output isn't correct
32 Incorrect 18 ms 25436 KB Output isn't correct
33 Incorrect 27 ms 25712 KB Output isn't correct
34 Incorrect 25 ms 25688 KB Output isn't correct
35 Incorrect 18 ms 25692 KB Output isn't correct
36 Incorrect 25 ms 25708 KB Output isn't correct
37 Incorrect 26 ms 25692 KB Output isn't correct
38 Incorrect 20 ms 25500 KB Output isn't correct
39 Incorrect 27 ms 25712 KB Output isn't correct
40 Incorrect 28 ms 25692 KB Output isn't correct
41 Incorrect 26 ms 25716 KB Output isn't correct
42 Incorrect 33 ms 25636 KB Output isn't correct
43 Incorrect 29 ms 25688 KB Output isn't correct
44 Incorrect 25 ms 25692 KB Output isn't correct
45 Incorrect 30 ms 25436 KB Output isn't correct
46 Incorrect 28 ms 25436 KB Output isn't correct
47 Incorrect 28 ms 25432 KB Output isn't correct
48 Incorrect 31 ms 25432 KB Output isn't correct
49 Incorrect 30 ms 25436 KB Output isn't correct
50 Incorrect 31 ms 25436 KB Output isn't correct
51 Incorrect 33 ms 25580 KB Output isn't correct
52 Incorrect 32 ms 25436 KB Output isn't correct
53 Incorrect 34 ms 25432 KB Output isn't correct
54 Incorrect 32 ms 25432 KB Output isn't correct
55 Incorrect 31 ms 25436 KB Output isn't correct
56 Incorrect 38 ms 25436 KB Output isn't correct
57 Incorrect 35 ms 25436 KB Output isn't correct
58 Incorrect 33 ms 25432 KB Output isn't correct
59 Incorrect 42 ms 25432 KB Output isn't correct
60 Incorrect 37 ms 25692 KB Output isn't correct
61 Incorrect 34 ms 25688 KB Output isn't correct
62 Incorrect 51 ms 25688 KB Output isn't correct
63 Incorrect 105 ms 25696 KB Output isn't correct
64 Incorrect 174 ms 25700 KB Output isn't correct
65 Incorrect 166 ms 25692 KB Output isn't correct
66 Incorrect 136 ms 25684 KB Output isn't correct
67 Correct 108 ms 25692 KB Output is correct
68 Incorrect 49 ms 25684 KB Output isn't correct
69 Incorrect 51 ms 25784 KB Output isn't correct
70 Incorrect 49 ms 25680 KB Output isn't correct
71 Incorrect 50 ms 25684 KB Output isn't correct
72 Correct 37 ms 25692 KB Output is correct
73 Correct 34 ms 25688 KB Output is correct
74 Incorrect 54 ms 25660 KB Output isn't correct
75 Incorrect 59 ms 25692 KB Output isn't correct
76 Incorrect 51 ms 25776 KB Output isn't correct
77 Incorrect 51 ms 25692 KB Output isn't correct
78 Correct 50 ms 25692 KB Output is correct
79 Incorrect 53 ms 25688 KB Output isn't correct
80 Incorrect 61 ms 25684 KB Output isn't correct
81 Incorrect 56 ms 25768 KB Output isn't correct
82 Incorrect 57 ms 25944 KB Output isn't correct
83 Incorrect 57 ms 25692 KB Output isn't correct
84 Incorrect 57 ms 25752 KB Output isn't correct
85 Incorrect 55 ms 25692 KB Output isn't correct
86 Incorrect 63 ms 25940 KB Output isn't correct
87 Incorrect 66 ms 25688 KB Output isn't correct
88 Incorrect 56 ms 25692 KB Output isn't correct
89 Incorrect 61 ms 25684 KB Output isn't correct
90 Incorrect 71 ms 25684 KB Output isn't correct
91 Incorrect 66 ms 25676 KB Output isn't correct
92 Incorrect 57 ms 25632 KB Output isn't correct