oj.uz

Submission #93712

# Submission time Handle Problem Language Result Execution time Memory
93712 2019-01-10T22:18:49 Z nikolapesic2802 Robots (APIO13_robots) C++14
10 / 100
 86 ms 57248 KB 
#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*N;
int n,h,w;
vector<int> dx={-1,0,1,0},dy={0,1,0,-1};
pair<int,int> dest[H][H][4];
vector<string> board;
bool end(int i,int j)
{
    return i<0||i>=h||j<0||j>=w||board[i][j]=='x';
}
void sub(int &a,int b)
{
    a-=b;
    if(a<0)
        a+=4;
}
void add(int &a,int b)
{
    a+=b;
    if(a>=4)
        a-=4;
}
pair<int,int> dfs(int i,int j,int p)
{
    if(end(i,j))
        return make_pair(-1,-1);
    if(board[i][j]=='A')
        add(p,-1);
    if(board[i][j]=='C')
        add(p,1);
    i+=dx[p];
    j+=dy[p];
    if(end(i,j))
        return make_pair(i-dx[p],j-dy[p]);
    return dfs(i,j,p);
}
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])
        {
            int x=p.f;
            int y=p.s;
            for(int p=0;p<4;p++)
                update(k,dest[x][y][p].f,dest[x][y][p].s,i+1);
        }
        q[i].clear();
    }
}
int main()
{
	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++)
                dest[i][j][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);
        }
    }
    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

robots.cpp: In function 'int main()':
robots.cpp:89: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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 57208 KB Output is correct
2 Correct 83 ms 57208 KB Output is correct
3 Correct 78 ms 57248 KB Output is correct
4 Correct 73 ms 57180 KB Output is correct
5 Correct 77 ms 57208 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 57208 KB Output is correct
2 Correct 83 ms 57208 KB Output is correct
3 Correct 78 ms 57248 KB Output is correct
4 Correct 73 ms 57180 KB Output is correct
5 Correct 77 ms 57208 KB Output is correct
6 Correct 86 ms 57208 KB Output is correct
7 Correct 67 ms 57208 KB Output is correct
8 Incorrect 79 ms 57208 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 57208 KB Output is correct
2 Correct 83 ms 57208 KB Output is correct
3 Correct 78 ms 57248 KB Output is correct
4 Correct 73 ms 57180 KB Output is correct
5 Correct 77 ms 57208 KB Output is correct
6 Correct 86 ms 57208 KB Output is correct
7 Correct 67 ms 57208 KB Output is correct
8 Incorrect 79 ms 57208 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 57208 KB Output is correct
2 Correct 83 ms 57208 KB Output is correct
3 Correct 78 ms 57248 KB Output is correct
4 Correct 73 ms 57180 KB Output is correct
5 Correct 77 ms 57208 KB Output is correct
6 Correct 86 ms 57208 KB Output is correct
7 Correct 67 ms 57208 KB Output is correct
8 Incorrect 79 ms 57208 KB Output isn't correct
9 Halted 0 ms 0 KB -