oj.uz

Submission #40562

# Submission time Handle Problem Language Result Execution time Memory
40562 2018-02-04T19:08:42 Z Hassoony Portal (COCI17_portal) C++14
120 / 120
 212 ms 43536 KB 
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
const ll inf=(1ll<<60);
const ll mod=1e9+7;
const int MX=550;
int n,m,vis[MX*MX];
ll dis[MX*MX];
char a[MX][MX];
bool b=0;
vector<pair<int,ll> >v[MX*MX];
int getnode(int x,int y){
    return ((x<<9)|y);
}
int getmin(int x1,int x2,int x3,int x4){
    return min(x1,min(x2,min(x3,x4)));
}
void dfs(int x,int y){
    if(vis[x])return;
    if(x==y){
        b=1;
        return;
    }
    vis[x]=1;
    for(auto pp:v[x]){
        dfs(pp.first,y);
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            a[i][j]='#';
        }
    }
    for(int i=1;i<=n;i++)scanf("%s",&a[i]+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='#')continue;
            v[getnode(i,j)].push_back({getnode(i-1,j),1});
            v[getnode(i,j)].push_back({getnode(i+1,j),1});
            v[getnode(i,j)].push_back({getnode(i,j-1),1});
            v[getnode(i,j)].push_back({getnode(i,j+1),1});
            int u=i+1,l=j-1,d=i-1,r=j+1;
            for(int k=j-1;k>=0;k--){
                if(a[i][k]=='#'){
                    l=k+1;
                    break;
                }
            }
            for(int k=j+1;k<=m+1;k++){
                if(a[i][k]=='#'){
                    r=k-1;
                    break;
                }
            }
            for(int k=i-1;k>=0;k--){
                if(a[k][j]=='#'){
                    u=k+1;
                    break;
                }
            }
            for(int k=i+1;k<=n+1;k++){
                if(a[k][j]=='#'){
                    d=k-1;
                    break;
                }
            }
            if(u!=i)v[getnode(i,j)].push_back({getnode(u,j),getmin(i-u,j-l+1,r-j+1,d-i+1)});
            if(d!=i)v[getnode(i,j)].push_back({getnode(d,j),getmin(d-i,j-l+1,r-j+1,i-u+1)});
            if(l!=j)v[getnode(i,j)].push_back({getnode(i,l),getmin(j-l,i-u+1,d-i+1,r-j+1)});
            if(r!=j)v[getnode(i,j)].push_back({getnode(i,r),getmin(r-j,i-u+1,d-i+1,j-l+1)});
        }
    }
    int x1,x2;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='C')x1=getnode(i,j);
            if(a[i][j]=='F')x2=getnode(i,j);
        }
    }
    dfs(x1,x2);
    if(!b){
        puts("nemoguce");
        return 0;
    }
    priority_queue<pair<ll,int> >pq;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dis[getnode(i,j)]=1e8;
            vis[getnode(i,j)]=0;
        }
    }
    dis[x1]=0;
    pq.push({0,x1});
    while(!pq.empty()){
        int x=pq.top().second;
        ll c=-pq.top().first;pq.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(auto pp:v[x]){
            if(pp.second+c<dis[pp.first]){
                dis[pp.first]=pp.second+c;
                pq.push({-dis[pp.first],pp.first});
            }
        }
    }
    cout<<dis[x2]<<endl;
}

Compilation message

portal.cpp: In function 'int main()':
portal.cpp:37:44: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[550]' [-Wformat=]
     for(int i=1;i<=n;i++)scanf("%s",&a[i]+1);
                                            ^
portal.cpp:37:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%s",&a[i]+1);
                                             ^
portal.cpp:76:9: warning: 'x1' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int x1,x2;
         ^
portal.cpp:76:12: warning: 'x2' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int x1,x2;
            ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7416 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7648 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7648 KB Output is correct
2 Correct 7 ms 7724 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7724 KB Output is correct
2 Correct 7 ms 7828 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7828 KB Output is correct
2 Correct 7 ms 7828 KB Output is correct
3 Correct 7 ms 7828 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 11500 KB Output is correct
2 Correct 11 ms 11500 KB Output is correct
3 Correct 20 ms 11500 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15084 KB Output is correct
2 Correct 12 ms 15084 KB Output is correct
3 Correct 24 ms 15084 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 29684 KB Output is correct
2 Correct 74 ms 29684 KB Output is correct
3 Correct 64 ms 29684 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 36460 KB Output is correct
2 Correct 61 ms 36460 KB Output is correct
3 Correct 105 ms 36460 KB Output is correct
4 Correct 86 ms 36460 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 43536 KB Output is correct
2 Correct 70 ms 43536 KB Output is correct
3 Correct 181 ms 43536 KB Output is correct
4 Correct 189 ms 43536 KB Output is correct