oj.uz

Submission #889110

# Submission time Handle Problem Language Result Execution time Memory
889110 2023-12-18T22:36:57 Z Maite_Morale Maze (JOI23_ho_t3) C++14
0 / 100
 175 ms 381524 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define X first
#define Y second
#define MAX 6000005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
#define ppp pair<pair<pll,pll>,pll>

pll d[4]={{0,1},{0,-1},{1,0},{-1,0}},s,e;
string a[MAX],asd;ll m,k,n;
ppp inv(ppp h){
    h.F.F.F*=-1;h.F.F.S*=-1;
    h.F.S.F*=-1;h.F.S.S*=-1;
return h;
}
int main(){
    fast_in
    cin>>n>>m>>k>>s.X>>s.Y>>e.X>>e.Y;
    for(int i=0;i<=m+1;i++){
        a[0]+='*';a[n+1]='*';
    }
    for(int i=1;i<=n;i++){
        cin>>asd;
        a[i]+='*';a[i]+=asd;a[i]+='*';
    }
    priority_queue<ppp> q;
    vector<vll> pass(n+5,vll(m+5,-1));
    q.push(inv({{{0,k},{k,k}},s}));  
    while(!q.empty()){
        ppp u=inv(q.top());q.pop();
        if(pass[u.S.X][u.S.Y]!=-1)continue;
        if(u.S.X==e.X && u.S.Y==e.Y){cout<<u.F.F.F;return 0;}
        //  cout<<u.S.X<<" "<<u.S.Y<<" "<<u.F.F.F<<" "<<u.F.F.S<<" "<<u.F.S.F<<" "<<u.F.S.S<<"\n";
        pass[u.S.X][u.S.Y]=u.F.F.F;
        for(int i=0;i<4;i++){
            pll w1={u.S.X+d[i].F,u.S.Y+d[i].S};
            if(a[w1.X][w1.Y]=='*')continue;
            ppp w={u.F,w1};
            if(w.F.F.S==k){
                if(a[w1.X][w1.Y]=='.'){
                    q.push(inv(w));continue;
                }
                //  cout<<w1.X<<" "<<w1.Y<<"\n";
                w.F={{w.F.F.F+1,0},{0,0}};
            }
            w.F.S.F+=abs(d[i].F);
            w.F.S.S+=abs(d[i].S);
            w.F.F.S=max(w.F.S.F,w.F.S.S);
            q.push(inv(w));
        }
    }
return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 188260 KB Output is correct
2 Correct 36 ms 188240 KB Output is correct
3 Runtime error 170 ms 381364 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 188248 KB Output is correct
2 Correct 37 ms 188240 KB Output is correct
3 Correct 38 ms 188248 KB Output is correct
4 Correct 37 ms 188240 KB Output is correct
5 Runtime error 162 ms 381524 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 188248 KB Output is correct
2 Correct 36 ms 188088 KB Output is correct
3 Correct 37 ms 188224 KB Output is correct
4 Correct 39 ms 188284 KB Output is correct
5 Correct 38 ms 188240 KB Output is correct
6 Correct 38 ms 188244 KB Output is correct
7 Correct 37 ms 188240 KB Output is correct
8 Correct 37 ms 188244 KB Output is correct
9 Correct 36 ms 188244 KB Output is correct
10 Runtime error 175 ms 381472 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 188248 KB Output is correct
2 Correct 37 ms 188240 KB Output is correct
3 Correct 38 ms 188248 KB Output is correct
4 Correct 37 ms 188240 KB Output is correct
5 Runtime error 162 ms 381524 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 188248 KB Output is correct
2 Correct 37 ms 188240 KB Output is correct
3 Correct 38 ms 188248 KB Output is correct
4 Correct 37 ms 188240 KB Output is correct
5 Runtime error 162 ms 381524 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 188260 KB Output is correct
2 Correct 36 ms 188240 KB Output is correct
3 Runtime error 170 ms 381364 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 188260 KB Output is correct
2 Correct 36 ms 188240 KB Output is correct
3 Runtime error 170 ms 381364 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 188260 KB Output is correct
2 Correct 36 ms 188240 KB Output is correct
3 Runtime error 170 ms 381364 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -