oj.uz

Submission #578600

# Submission time Handle Problem Language Result Execution time Memory
578600 2022-06-17T10:58:19 Z MohammadAghil Robots (APIO13_robots) C++17
60 / 100
 1500 ms 112788 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) x.begin(), x.end()
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 5e2 + 5, lg = 10, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

int st[maxn][maxn], n, m, k;
pp ply[lg], adj[maxn][maxn][4];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool vis[maxn][maxn][4];
int dist[lg][lg][maxn][maxn];

pp dfs(int x, int y, int dir){
     if(vis[x][y][dir]) return adj[x][y][dir];
     adj[x][y][dir] = {-1, -1};
     vis[x][y][dir] = true;
     int d = dir;
     if(st[x][y] == 2) d = (d + 3)%4;
     if(st[x][y] == 3) d = (d + 1)%4;
     int i = x + dx[d], j = y + dy[d];
     if(i < 0 || i == n || j < 0 || j == m || !st[i][j]) return adj[x][y][dir] = {x, y};
     return adj[x][y][dir] = dfs(i, j, d);
}

int main(){
     cin.tie(0) -> sync_with_stdio(0);
     cin >> k >> m >> n;
     rep(i,0,n) rep(j,0,m){
          char c; cin >> c;
          if(c == '.') st[i][j] = 1;
          if(c == 'A') st[i][j] = 2;
          if(c == 'C') st[i][j] = 3;
          if(c >= '0' && c <= '9') st[i][j] = 1, ply[c-'1'] = {i, j};
     }
     rep(i,0,n) rep(j,0,m) rep(d,0,4) dfs(i, j, d);

     rep(i,0,lg) rep(j,0,lg) rep(t,0,n) rep(f,0,m) dist[i][j][t][f] = inf;

     rep(t,0,k){
          deque<pp> q{ply[t]}; dist[t][t][ply[t].ff][ply[t].ss] = 0;
          while(sz(q)){
               auto[x, y] = q.front(); q.pop_front();
               rep(d,0,4) if(adj[x][y][d].ff + 1 && dist[t][t][adj[x][y][d].ff][adj[x][y][d].ss] == inf){
                    q.push_back(adj[x][y][d]);
                    dist[t][t][adj[x][y][d].ff][adj[x][y][d].ss] = dist[t][t][x][y] + 1;
               }
          }
     }

     rep(l,2,k+1){
          rep(i,0,k-l+1){
               int j = i + l - 1;

               priority_queue<pair<int, pp>, vector<pair<int, pp>>, greater<pair<int, pp>>> q;
               rep(x,0,n) rep(y,0,m){
                    rep(m,i,j){
                         dist[i][j][x][y] = min(dist[i][j][x][y], dist[i][m][x][y] + dist[m+1][j][x][y]);
                    }
                    if(dist[i][j][x][y] - inf) q.push({dist[i][j][x][y], {x, y}});
               }

               while(sz(q)){
                    auto[w, t] = q.top(); q.pop();
                    auto[x, y] = t;
                    if(w - dist[i][j][x][y]) continue;
                    rep(d,0,4){
                         auto[xp, yp] = adj[x][y][d];
                         if(xp + 1 && dist[i][j][xp][yp] > w + 1){
                              q.push({dist[i][j][xp][yp] = w + 1, {xp, yp}});
                         }
                    }
               }
          }
     }

     int ans = inf;
     rep(i,0,n) rep(j,0,m) ans = min(ans, dist[0][k-1][i][j]);
     cout << (ans == inf? -1: ans) << '\n';
     return 0; 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 127 ms 65452 KB Output is correct
12 Correct 34 ms 64720 KB Output is correct
13 Correct 43 ms 65296 KB Output is correct
14 Correct 538 ms 66136 KB Output is correct
15 Correct 86 ms 65208 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 127 ms 65452 KB Output is correct
12 Correct 34 ms 64720 KB Output is correct
13 Correct 43 ms 65296 KB Output is correct
14 Correct 538 ms 66136 KB Output is correct
15 Correct 86 ms 65208 KB Output is correct
16 Correct 107 ms 109720 KB Output is correct
17 Execution timed out 1540 ms 112788 KB Time limit exceeded
18 Halted 0 ms 0 KB -