oj.uz

Submission #991747

# Submission time Handle Problem Language Result Execution time Memory
991747 2024-06-03T05:09:37 Z vjudge1 Robots (APIO13_robots) C++17
10 / 100
 1500 ms 4604 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define all(cont) ls.begin(), ls.end()
#define rall(cont) ls.rbegin(), ls.rend()
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 998244353
#define ll long long
#define vl vector<ll>
#define pl pair<ll,ll>
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
//template <class T>
//using Tree = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;//use to count elements lesser than x in an ordered set and in constant time
// ~-~-~-~-~-~-~-~-~-~ MAIN CODE  ~-~-~-~-~-~-~-~-~
char grid[505][505];
ll dist1[505][505];
ll dist2[505][505];
bool visited1[505][505];
bool visited2[505][505];
vector<vector<vector<pl>>>graph;
ll t=1,n,w,h;
bool valid(int x,int y){
    return (x>=0 and y>=0 and x<w and y<h and grid[y][x]!='x');
}
pl valid_after(ll x,ll y,ll d){
  while(true){
    if(grid[y][x]=='A'){
        d-=1;
        d+=4; 
        d%=4;
    }
    if(grid[y][x]=='C'){
        d+=3; 
        d%=4;
    }
    if(d==0){
        if(!valid(x-1,y)){
          return {x,y};
        }
        else{
          x--;
        }
    }
    else if(d==1){
        if(!valid(x,y-1)){
          return {x,y};
        }
        else{
          y--;
        }
    }
    else if(d==2){
        if(!valid(x+1,y)){
          return {x,y};
        }
        else{
          x++;
        }
    }
    else if(d==3){
        if(!valid(x,y+1)){
          return {x,y};
        }
        else{
          y++;
        }
    }
  }
}
void solve(){
  cin>>n>>w>>h;
  ll x1,x2,y1,y2;
  for(int i=0;i<h;i++){
    vector<vector<pl>>chh;
    for(int j=0;j<w;j++){
      vector<pl>cc;
      chh.PB(cc);
      cin>>grid[i][j];
      dist1[i][j]=1e9;
      dist2[i][j]=1e9;
      if(grid[i][j]=='1'){
        x1=j;
        y1=i;
        dist1[i][j]=0;
        visited1[i][j]=1;
      }
      if(grid[i][j]=='2'){
        x2=j;
        y2=i;
        dist2[i][j]=0;
        visited2[i][j]=1;
      }
    }
    graph.PB(chh);
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      for(int k=0;k<4;k++){
        pl ch=valid_after(j,i,k);
        if(ch.first!=j or ch.second!=i){
          graph[i][j].PB(ch);
        }
      }
    }   
  }
  queue<pair<pl,pl>>q;
  for(auto i:graph[y1][x1]){
    q.push({i,{x1,y1}});
  }
  while(!q.empty()){
    pair<pl,pl>curr=q.front();q.pop();
    ll x=curr.first.first,y=curr.first.second,pre_x=curr.second.first,pre_y=curr.second.second;
    if(!visited1[y][x]){
      dist1[y][x]=min(dist1[y][x],dist1[pre_y][pre_x]+1);
      visited1[y][x]=true;
      for(auto i:graph[y][x]){
        q.push({i,{x, y}});
      }
    }
  }
  for(auto i:graph[y2][x2]){
    q.push({i,{x2,y2}});
  }
  while(!q.empty()){
    pair<pl,pl>curr=q.front();q.pop();
    ll x=curr.first.first,y=curr.first.second,pre_x=curr.second.first,pre_y=curr.second.second;
    if(!visited2[y][x]){
      dist2[y][x]=min(dist2[y][x],dist2[pre_y][pre_x]+1);
      visited2[y][x]=true;
      for(auto i:graph[y][x]){
        q.push({i,{x, y}});
      }
    }
  }
  bool check=0;
  ll ans=1e9;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(dist1[i][j]!=1e9 and dist2[i][j]!=1e9){
          check=1;
          ans=min(ans,dist1[i][j]+dist2[i][j]);
      }
    }
  }
  if(check){
    cout<<ans;
  }
  else{
    cout<<-1;
  }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // cin>>t;
    for(int i=0;i<t;i++){
      solve();
    }
}

Compilation message

robots.cpp: In function 'void solve()':
robots.cpp:128:22: warning: 'y2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |   for(auto i:graph[y2][x2]){
      |                      ^
robots.cpp:128:26: warning: 'x2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |   for(auto i:graph[y2][x2]){
      |                          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4604 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4604 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Execution timed out 1598 ms 4444 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4604 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Execution timed out 1598 ms 4444 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4604 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Execution timed out 1598 ms 4444 KB Time limit exceeded
10 Halted 0 ms 0 KB -