Submission #577951

#	Time	Username	Problem	Language	Result	Execution time	Memory
577951		Iwanttobreakfree	Mecho (IOI09_mecho)	C++98	100 / 100	340 ms	41676 KiB

mecho

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfs(queue<int>& q,vector<int>& dist,vector<vector<int>>& g,int b){
    int n=dist.size();
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v:g[u]){
            if(dist[v]==-1&&v!=b){
                dist[v]=dist[u]+1;
                q.push(v);
            }
        }
    }
}
bool pos(int a,int b,int mid,int s,vector<vector<int>>& g,vector<int>& dist){
    int n=dist.size();
    vector<int> d(n,-1);
    queue<int> q;
    q.push(a);
    //cout<<mid<<'\n';
    if(mid>=dist[a])return false;
    d[a]=0;
    while(!q.empty()){
        int u=q.front();
        if(u==b)return true;
        q.pop();
        //cout<<d[u].first<<' ';
        for(int v:g[u]){
            if(d[v]==-1&&d[u]+1+1LL*mid*s<1LL*dist[v]*s){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    return false;
}
int main(){
    int n,s,u,v;
    char c;
    cin>>n>>s;
    vector<vector<int>> g(n*n,vector<int>());
    vector<vector<char>> grid(n,vector<char>(n));
    vector<int> dist(n*n,-1);
    queue<int> q;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>grid[i][j];
            if(grid[i][j]=='T')continue;
            else{
                if(i&&grid[i-1][j]!='T'){
                    g[i*n+j].push_back(i*n+j-n);
                    g[i*n+j-n].push_back(i*n+j);
                }
                if(j&&grid[i][j-1]!='T'){
                    g[i*n+j].push_back(i*n+j-1);
                    g[i*n+j-1].push_back(i*n+j);
                }
                if(grid[i][j]=='D'){
                    v=i*n+j;
                    dist[v]=1e9;
                }
                if(grid[i][j]=='M')u=i*n+j;
                if(grid[i][j]=='H'){
                    q.push(i*n+j);
                    dist[i*n+j]=0;
                }
            }
        }
    }
    bfs(q,dist,g,v);
    int l=0,r=1e9,ans=-1;
    while(l<=r){
        int mid=(r+l)/2;
        if(pos(u,v,mid,s,g,dist)){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    cout<<ans;
}

Compilation message (stderr)

mecho.cpp: In function 'void bfs(std::queue<int>&, std::vector<int>&, std::vector<std::vector<int> >&, int)':
mecho.cpp:6:9: warning: unused variable 'n' [-Wunused-variable]
    6 |     int n=dist.size();
      |         ^
mecho.cpp: In function 'int main()':
mecho.cpp:42:10: warning: unused variable 'c' [-Wunused-variable]
   42 |     char c;
      |          ^
mecho.cpp:77:15: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |         if(pos(u,v,mid,s,g,dist)){
      |            ~~~^~~~~~~~~~~~~~~~~~
mecho.cpp:77:15: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 100 / 100