Submission #1342997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1342997		ghunglt	Mecho (IOI09_mecho)	C++20	4 / 100	643 ms	15384 KiB

mecho

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

const int N=805, inf=1e9;
const int dx[]={1,-1,0,0}, dy[]={0,0,1,-1};
int n, s, dist1[N][N], dist2[N][N], xM, yM, xD, yD, best[N][N];
pair<int,int> trace[N][N];
string mat[N];

struct state{
    int times, steps, x, y;

    bool operator<(const state other)const{
        return times>other.times;
    }
};

bool valid(int x,int y){
    return x>=0 && x<n && y>=0 && y<n;
}

void bfs(int sx,int sy){
    dist1[sx][sy]=1;
    queue<pair<int,int>> q;
    q.push({sx,sy});

    while (q.size()){
        auto [x, y]=q.front();
        q.pop();

        for (int i=0;i<4;i++){
            int nx=x+dx[i], ny=y+dy[i];
            if (valid(nx,ny) && mat[nx][ny]=='G' && dist1[nx][ny]>dist1[x][y]+1){
                dist1[nx][ny]=dist1[x][y]+1;
                q.push({nx,ny});
            }
        }
    }
}

void dijkstra(int sx,int sy){
    trace[sx][sy]={-1,-1};
    priority_queue<state> pq;
    pq.push({0,0,sx,sy});
    dist2[sx][sy]=0;
    best[sx][sy]=0;

    while (pq.size()){
        auto [times, steps, x, y]=pq.top();
        pq.pop();

        if (times>dist2[x][y]) continue;
        if (times==dist2[x][y] && steps<best[x][y]) continue;

        if (x==xD && y==yD) break;

        for (int i=0;i<4;i++){
            int nx=x+dx[i], ny=y+dy[i];
            if (valid(nx,ny) && (mat[nx][ny]=='G' || mat[nx][ny]=='D')){
                // Di trong 1 phut
                int nt, ns;
                if (steps<s){
                    nt=times, ns=steps+1;
                    if (nt<dist2[nx][ny] || (nt==dist2[nx][ny] && ns>best[nx][ny])){
                        dist2[nx][ny]=nt;
                        best[nx][ny]=ns;
                        trace[nx][ny]={x,y};
                        pq.push({nt,ns,nx,ny});
                    }
                }
                // Qua phut moi
                nt=times+1, ns=steps+1;
                if (nt<dist2[nx][ny] || (nt==dist2[nx][ny] && ns>best[nx][ny])){
                    dist2[nx][ny]=nt;
                    best[nx][ny]=ns;
                    trace[nx][ny]={x,y};
                    pq.push({nt,ns,nx,ny});
                }
            }
        }
    }

    auto [ex, ey]=trace[xD][yD];
    if (dist1[ex][ey]<=dist2[ex][ey]){
        cout<<-1;
        return;
    }
    cout<<dist1[ex][ey]<<' '<<dist2[ex][ey]<<'\n'; 
    cout<<dist1[ex][ey]/dist2[ex][ey]-1;
}

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

    cin>>n>>s;
    for (int i=0;i<n;i++) cin>>mat[i];

    fill(&dist1[0][0],&dist1[0][0]+N*N,inf);
    fill(&dist2[0][0],&dist2[0][0]+N*N,inf);
    fill(&best[0][0],&best[0][0]+N*N,-1);
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (mat[i][j]=='M'){
                xM=i;
                yM=j;
            }
            if (mat[i][j]=='H') bfs(i,j);
            if (mat[i][j]=='D'){
                xD=i;
                yD=j;
            }
        }
    }

    dijkstra(xM,yM);

    return 0;
}

• Subtask 1: 4 / 100