Submission #93731

#	Time	Username	Problem	Language	Result	Execution time	Memory
93731		nikolapesic2802	Robots (APIO13_robots)	C++14	100 / 100	913 ms	103328 KiB

robots

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
const int N=9;
const int H=500;
const int maxDist=H*H;
int n,h,w;
vector<int> dx={-1,0,1,0},dy={0,1,0,-1};
pair<int,int> dest[H][H][4],null={-1,-1};
vector<string> board;
bool end(int i,int j)
{
    return i<0||i>=h||j<0||j>=w||board[i][j]=='x';
}
void add(int &a,int b)
{
    a+=b;
    if(a>=4)
        a-=4;
    if(a<0)
        a+=4;
}
pair<int,int> dfs(int i,int j,int p)
{
    if(dest[i][j][p]!=null)
        return dest[i][j][p];
    int np=p;
    if(board[i][j]=='A')
        add(np,-1);
    if(board[i][j]=='C')
        add(np,1);
    int ni=i+dx[np];
    int nj=j+dy[np];
    if(end(ni,nj))
        return dest[i][j][p]=make_pair(i,j);
    return dest[i][j][p]=dfs(ni,nj,np);
}
vector<vector<vector<int> > > dp;
vector<vector<int> > initial_dp(H,vector<int>(H,(int)1e9));
int mask[H][H];
vector<pair<int,int> > q[maxDist];
void update(int k,int x,int y,int d)
{
    if(d<dp[k][x][y])
    {
        dp[k][x][y]=d;
        q[d].pb({x,y});
    }
}
void bfs(int k)
{
    for(int i=0;i<maxDist;i++)
        for(auto p:q[i])
            if(dp[k][p.f][p.s]>=i)
                for(int l=0;l<4;l++)
                    update(k,dest[p.f][p.s][l].f,dest[p.f][p.s][l].s,i+1);
}
int main()
{
    for(int i=0;i<H;i++)
        for(int j=0;j<H;j++)
            for(int k=0;k<4;k++)
                dest[i][j][k]=null;
	scanf("%i %i %i",&n,&h,&w);
	swap(h,w);
	board.resize(h);
	for(int i=0;i<h;i++)
        cin >> board[i];
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
            for(int k=0;k<4;k++)
                dfs(i,j,k);
    vector<pair<int,int> > pos(n);
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
        {
            int t=board[i][j]-'0';
            if(t>0&&t<10)
                pos[t-1]=make_pair(i,j);
        }
    for(int i=0,k=0;i<n;i++)
    {
        for(int j=i;j>=0;j--,k++)
        {
            mask[j][i]=k;
            dp.pb(initial_dp);
            if(j==i)
                update(k,pos[j].f,pos[j].s,0);
            else
                for(int x=0;x<h;x++)
                    for(int y=0;y<w;y++)
                        for(int l=j;l<i;l++)
                            update(k,x,y,dp[mask[j][l]][x][y]+dp[mask[l+1][i]][x][y]);
            bfs(k);
            for(int l=0;l<maxDist;l++)
                q[l].clear();
        }
    }
    int ans=1e9;
    for(int x=0;x<h;x++)
        for(int y=0;y<w;y++)
            ans=min(ans,dp[mask[0][n-1]][x][y]);
    if(ans==(int)1e9)
        printf("-1\n");
    else
        printf("%i\n",ans);
    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:80:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=0;i<H;i++)
     ^~~
robots.cpp:84:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  scanf("%i %i %i",&n,&h,&w);
  ^~~~~
robots.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&h,&w);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40