oj.uz

Submission #940999

# Submission time Handle Problem Language Result Execution time Memory
940999 2024-03-08T04:53:15 Z Faisal_Saqib Portals (BOI14_portals) C++17
70 / 100
 40 ms 44124 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+1;
char grid[N][N];
bool vis[N][N];
int n,m;
vector<pair<int,int>> dir={{0,1},{0,-1},{1,0},{-1,0}};
bool valid(int i,int j)
{
    if(min(i,j)>=0 and i<n and j<m and grid[i][j]!='#')
        return 1;
    return 0;
}
int dist[N][N],before[N][N],after[N][N],up[N][N],down[N][N];
void dp(int sx,int sy)
{
  dist[sx][sy]=0;
  priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
  pq.push({0,{sx,sy}});
  while(pq.size())
  {
    auto tp=pq.top();
    pq.pop();
    int dip=tp.first;
    pair<int,int> pt=tp.second;
    if(dist[pt.first][pt.second]==dip)
    {
        // cout<<"Hola "<<pt.first<<' '<<pt.second<<' '<<dip<<endl;
        vis[pt.first][pt.second]=1;
        for(int j=0;j<4;j++)
        {
            if(valid(pt.first+dir[j].first,pt.second+dir[j].second) and dist[pt.first+dir[j].first][pt.second+dir[j].second]>dip+1)
            {
                dist[pt.first+dir[j].first][pt.second+dir[j].second]=dip+1;
                pq.push({dip+1,{pt.first+dir[j].first,pt.second+dir[j].second}});
            }
        }
        // Go to Up first
        {
            // Up
            int j=up[pt.first][pt.second];
            int jp=down[pt.first][pt.second];
            int curd=dip+(pt.first-j);
            if(curd<dist[jp-1][pt.second])
            {
                dist[jp-1][pt.second]=curd;
                pq.push({curd,{jp-1,pt.second}});
            }

            jp=before[pt.first][pt.second];
            if(curd<dist[pt.first][jp+1])
            {
                dist[pt.first][jp+1]=curd;
                pq.push({curd,{pt.first,jp+1}});
            }

            jp=after[pt.first][pt.second];
            if(curd<dist[pt.first][jp-1])
            {
                dist[pt.first][jp-1]=curd;
                pq.push({curd,{pt.first,jp-1}});
            }
        }

        {
            // Down
            int j=down[pt.first][pt.second];
            int jp=up[pt.first][pt.second];
            int curd=dip+(j-pt.first);
            if(curd<dist[jp+1][pt.second])
            {
                dist[jp+1][pt.second]=curd;
                pq.push({curd,{jp+1,pt.second}});
            }

            jp=before[pt.first][pt.second];
            if(curd<dist[pt.first][jp+1])
            {
                dist[pt.first][jp+1]=curd;
                pq.push({curd,{pt.first,jp+1}});
            }

            jp=after[pt.first][pt.second];
            if(curd<dist[pt.first][jp-1])
            {
                dist[pt.first][jp-1]=curd;
                pq.push({curd,{pt.first,jp-1}});
            }
        }

        {
            // Down
            int j=before[pt.first][pt.second];
            int curd=dip+(pt.second-j);
            int jp=up[pt.first][pt.second];
            if(curd<dist[jp+1][pt.second])
            {
                dist[jp+1][pt.second]=curd;
                pq.push({curd,{jp+1,pt.second}});
            }

            jp=down[pt.first][pt.second];
            if(curd<dist[jp-1][pt.second])
            {
                dist[jp-1][pt.second]=curd;
                pq.push({curd,{jp-1,pt.second}});
            }

            jp=after[pt.first][pt.second];
            if(curd<dist[pt.first][jp-1])
            {
                dist[pt.first][jp-1]=curd;
                pq.push({curd,{pt.first,jp-1}});
            }
        }

        {
            // Down
            int j=after[pt.first][pt.second];
            int curd=dip+(j-pt.second);
            int jp=up[pt.first][pt.second];
            if(curd<dist[jp+1][pt.second])
            {
                dist[jp+1][pt.second]=curd;
                pq.push({curd,{jp+1,pt.second}});
            }

            jp=down[pt.first][pt.second];
            if(curd<dist[jp-1][pt.second])
            {
                dist[jp-1][pt.second]=curd;
                pq.push({curd,{jp-1,pt.second}});
            }

            jp=before[pt.first][pt.second];
            if(curd<dist[pt.first][jp+1])
            {
                dist[pt.first][jp+1]=curd;
                pq.push({curd,{pt.first,jp+1}});
            }
        }
    }
  }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    n+=2;
    m+=2;
    int sx=0,sy=0,cx,cy;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(i==0 or j==0 or i==n-1 or j==m-1)
            {
                grid[i][j]='#';
            }
            else{
                cin>>grid[i][j];
                if(grid[i][j]=='S')
                {
                    sx=i;
                    sy=j;
                }
                if(grid[i][j]=='C')
                {
                    cx=i;
                    cy=j;
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            dist[i][j]=1e9;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(grid[i][j]=='#')
            {
                before[i][j]=j;
            }
            else{
                before[i][j]=before[i][j-1];
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=m-1;j>=0;j--)
        {
            if(grid[i][j]=='#')
            {
                after[i][j]=j;
            }
            else{
                after[i][j]=after[i][j+1];
            }
        }
    }
    for(int j=0;j<m;j++)
    {
        for(int i=0;i<n;i++)
        {
            if(grid[i][j]=='#')
            {
                up[i][j]=i;
            }
            else{
                up[i][j]=up[i-1][j];
            }
        }
    }
    for(int j=0;j<m;j++)
    {
        for(int i=n-1;i>=0;i--)
        {
            if(grid[i][j]=='#')
            {
                down[i][j]=i;
            }
            else{
                down[i][j]=down[i+1][j];
            }
        }
    }
    // for(int i=0;i<n;i++)
    // {
    //     for(int j=0;j<m;j++)
    //     {
    //         cout<<grid[i][j];
    //     }
    //     cout<<endl;;
    // }  
    dp(sx,sy);
    cout<<dist[cx][cy]<<endl;
    return 0;
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:245:22: warning: 'cy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  245 |     cout<<dist[cx][cy]<<endl;
      |                      ^
portals.cpp:245:22: warning: 'cx' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 1 ms 10588 KB Output is correct
10 Correct 1 ms 10588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 1 ms 10716 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 1 ms 10588 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10676 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 8 ms 18996 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 8 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10700 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12888 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 6 ms 19032 KB Output is correct
15 Correct 7 ms 19032 KB Output is correct
16 Correct 8 ms 19036 KB Output is correct
17 Correct 8 ms 19036 KB Output is correct
18 Correct 9 ms 19036 KB Output is correct
19 Correct 9 ms 19036 KB Output is correct
20 Correct 9 ms 19036 KB Output is correct
21 Correct 6 ms 19036 KB Output is correct
22 Correct 7 ms 19036 KB Output is correct
23 Correct 7 ms 19020 KB Output is correct
24 Correct 8 ms 19032 KB Output is correct
25 Correct 1 ms 10584 KB Output is correct
26 Correct 2 ms 12892 KB Output is correct
27 Correct 2 ms 10588 KB Output is correct
28 Correct 4 ms 19036 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10584 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10584 KB Output is correct
7 Correct 1 ms 10584 KB Output is correct
8 Correct 1 ms 10588 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 6 ms 19036 KB Output is correct
15 Correct 7 ms 19032 KB Output is correct
16 Correct 8 ms 19036 KB Output is correct
17 Correct 7 ms 19036 KB Output is correct
18 Correct 9 ms 19036 KB Output is correct
19 Correct 9 ms 19036 KB Output is correct
20 Correct 8 ms 19032 KB Output is correct
21 Correct 6 ms 19032 KB Output is correct
22 Correct 7 ms 19032 KB Output is correct
23 Correct 8 ms 19036 KB Output is correct
24 Runtime error 40 ms 44124 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -