Submission #726072

# Submission time Handle Problem Language Result Execution time Memory
726072 2023-04-18T12:23:09 Z vjudge1 Robots (APIO13_robots) C++17
Compilation error
0 ms 0 KB
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int inf=1e9;
int v1[]={-1,0,1,0};
int v2[]={0,1,0,-1};
char a[509][509];
pii nxt[509][509][4];
int dp[9][9][509][509];
vector<pii>g[509][509];
int vis[9][9];
pii pos[9];
int n,r,c;
pii cal(int i,int j,int hr){
    if (nxt[i][j][hr]!=pii(0,0))return nxt[i][j][hr];
    //cout<<i<<" "<<j<<" "<<hr<<'\n';
    int lt=hr;
    if (a[i][j]=='A')hr=(hr-1+4)%4;
    if (a[i][j]=='C')hr=(hr+1)%4;
    nxt[i][j][lt]={-1,-1};
    //cout<<i<<" "<<j<<" "<<hr<<" "<<lt<<'\n';
    int newi=i+v1[hr],newj=j+v2[hr];
    if (newi==0||newj==0||newi>r||newj>c||a[newi][newj]=='x')return nxt[i][j][lt]={i,j};
    return nxt[i][j][lt]=cal(newi,newj,hr);
}
int visit[509][509];
struct ver{
int i,j,dis;
bool operator < (const ver &p)const {
return dis>p.dis;
}
};
void cal(int l1,int r1){
if (vis[l1][r1])return;
vis[l1][r1]=1;
if (l1==r1){
    for1(i,1,r){
    for1(j,1,c){
    dp[l1][l1][i][j]=inf;
    }
    }
    dp[l1][l1][pos[l1].fi][pos[l1].se]=0;
    memset(visit,0,sizeof(visit));
    visit[pos[l1].fi][pos[l1].se]=1;
    queue<pii>t;
    t.push(pos[l1]);
    while (!t.empty()){
        auto u=t.front();
        t.pop();
        for (auto v:g[u.fi][u.se]){
            if (visit[v.fi][v.se])continue;
            visit[v.fi][v.se]=1;
            dp[l1][l1][v.fi][v.se]=dp[l1][l1][u.fi][u.se]+1;
            t.push(v);
        }
    }
    return;
}
for1(i,1,r){
for1(j,1,c){
dp[l1][r1][i][j]=inf;
}
}
for1(id,l1,r1-1){
cal(l1,id);
cal(id+1,r1);
for1(i,1,r){
for1(j,1,c){
dp[l1][r1][i][j]=min({dp[l1][r1][i][j],inf,dp[l1][id][i][j]+dp[id+1][r1][i][j]});
}
}
}
memset(visit,0,sizeof( visit));
vector<ver>vcl;
for1(i,1,r){
for1(j,1,c){
if (dp[l1][r1][i][j]>=inf)continue;
vcl.pb({i,j,dp[l1][r1][i][j]});
}
}
sort(all(vcl));
deque<ver>t;
while (sz(t)||sz(vcl)){
    if (t.empty()){
        t.pb(vcl.back());
        vcl.pop_back();
    }
    else {
        if (sz(vcl)){
            if (vcl.back().dis<t.front().dis){
            t.push_front(vcl.back());
            vcl.pop_back();
            }
        }
    }
    auto u=t.front();
    t.pop_front();
    //cout<<u.i<<" "<<u.j<<" "<<u.dis<<'\n';
    if (visit[u.i][u.j])continue;
    dp[l1][r1][u.i][u.j]=u.dis;
    visit[u.i][u.j]=1;
    for (auto v:g[u.i][u.j]){
        if (visit[v.fi][v.se])continue;
        ver ttt={v.fi,v.se,u.dis+1};
        //if (u.i==1&&u.j==7)cout<<u.dis+1<<'\n';
        t.pb(ttt);
    }
}
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    cin>>n>>c>>r;
    for1(i,1,r){
    for1(j,1,c){
    cin>>a[i][j];
    if (a[i][j]!='.'&&a[i][j]!='x'&&a[i][j]!='A'&&a[i][j]!='C'){
        pos[a[i][j]-'1']={i,j};
    }
    }
    }
    //cal(5,5,1);
    for1(i,1,r){
    for1(j,1,c){
    if (a[i][j]!='x'){
        for1(k,0,3){
        cal(i,j,k);
        if (nxt[i][j][k]!=pii(-1,-1)&&nxt[i][j][k]!=pii(i,j)){
            g[i][j].pb(nxt[i][j][k]);
        }
        }
    }
    }
    }
    //cal(5,5,1);
    cal(0,n-1);
    int ans=inf;
    for1(i,1,r){
    for1(j,1,c){
    ans=min(ans,dp[0][n-1][i][j]);
    }
    }
    //cal(2,3);
    //cout<<dp[2][3][1][1];
    if (ans>=inf)cout<<-1;
    else cout<<ans;
    //cout<<dp[2][3][1][1];
    //cout<<pos[2].fi<<" "<<pos[2].se;
    //cout<<nxt[pos[2].fi][pos[2].se][1].fi<<" "<<nxt[pos[2].fi][pos[2].se][1].se;

}

Compilation message

robots.cpp: In function 'void cal(int, int)':
robots.cpp:57:12: error: reference to 'visit' is ambiguous
   57 |     memset(visit,0,sizeof(visit));
      |            ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
                 from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1700 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
robots.cpp:40:5: note:                 'int visit [509][509]'
   40 | int visit[509][509];
      |     ^~~~~
robots.cpp:57:27: error: reference to 'visit' is ambiguous
   57 |     memset(visit,0,sizeof(visit));
      |                           ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
                 from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1700 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
robots.cpp:40:5: note:                 'int visit [509][509]'
   40 | int visit[509][509];
      |     ^~~~~
robots.cpp:58:5: error: reference to 'visit' is ambiguous
   58 |     visit[pos[l1].fi][pos[l1].se]=1;
      |     ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
                 from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1700 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
robots.cpp:40:5: note:                 'int visit [509][509]'
   40 | int visit[509][509];
      |     ^~~~~
robots.cpp:65:17: error: reference to 'visit' is ambiguous
   65 |             if (visit[v.fi][v.se])continue;
      |                 ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
                 from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1700 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
robots.cpp:40:5: note:                 'int visit [509][509]'
   40 | int visit[509][509];
      |     ^~~~~
robots.cpp:66:13: error: reference to 'visit' is ambiguous
   66 |             visit[v.fi][v.se]=1;
      |             ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
                 from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1700 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
robots.cpp:40:5: note:                 'int visit [509][509]'
   40 | int visit[509][509];
      |     ^~~~~
robots.cpp:87:8: error: reference to 'visit' is ambiguous
   87 | memset(visit,0,sizeof( visit));
      |        ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
                 from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1700 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
robots.cpp:40:5: note:                 'int visit [509][509]'
   40 | int visit[509][509];
      |     ^~~~~
robots.cpp:87:24: error: reference to 'visit' is ambiguous
   87 | memset(visit,0,sizeof( visit));
      |                        ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
                 from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1700 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
robots.cpp:40:5: note:                 'int visit [509][509]'
   40 | int visit[509][509];
      |     ^~~~~
robots.cpp:113:9: error: reference to 'visit' is ambiguous
  113 |     if (visit[u.i][u.j])continue;
      |         ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
                 from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1700 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
robots.cpp:40:5: note:                 'int visit [509][509]'
   40 | int visit[509][509];
      |     ^~~~~
robots.cpp:115:5: error: reference to 'visit' is ambiguous
  115 |     visit[u.i][u.j]=1;
      |     ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
                 from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1700 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
robots.cpp:40:5: note:                 'int visit [509][509]'
   40 | int visit[509][509];
      |     ^~~~~
robots.cpp:117:13: error: reference to 'visit' is ambiguous
  117 |         if (visit[v.fi][v.se])continue;
      |             ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
                 from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
 1700 |     visit(_Visitor&& __visitor, _Variants&&... __variants)
      |     ^~~~~
robots.cpp:40:5: note:                 'int visit [509][509]'
   40 | int visit[509][509];
      |     ^~~~~