oj.uz

Submission #578678

# Submission time Handle Problem Language Result Execution time Memory
578678 2022-06-17T14:35:59 Z MohammadAghil Robots (APIO13_robots) C++17
100 / 100
 738 ms 138760 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 + 1, lg = 9, 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[50][maxn][maxn], vl[lg][lg];
 
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;
     int id = 0;
     rep(i,0,k) rep(j,i,k) vl[i][j] = id++;
     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,id) rep(t,0,n) rep(f,0,m) dist[i][t][f] = inf;
 
     rep(t,0,k){
          deque<pp> q{ply[t]}; dist[vl[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[vl[t][t]][adj[x][y][d].ff][adj[x][y][d].ss] == inf){
                    q.push_back(adj[x][y][d]);
                    dist[vl[t][t]][adj[x][y][d].ff][adj[x][y][d].ss] = dist[vl[t][t]][x][y] + 1;
               }
          }
     }
 
     vector<vector<pp>> pos(k*n*m + 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[vl[i][j]][x][y] = min(dist[vl[i][j]][x][y], dist[vl[i][m]][x][y] + dist[vl[m+1][j]][x][y]);
                    }
                    if(dist[vl[i][j]][x][y] - inf) pos[dist[vl[i][j]][x][y]].pb({x, y});
                    dist[vl[i][j]][x][y] = inf;
               }
 
               // 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}});
               //           }
               //      }
               // }
 
               rep(s,0,sz(pos)){
                    for(auto[x, y]: pos[s]) if(dist[vl[i][j]][x][y] == inf){
                         dist[vl[i][j]][x][y] = s;
                         rep(d,0,4) if(adj[x][y][d].ff + 1 && dist[vl[i][j]][adj[x][y][d].ff][adj[x][y][d].ss] == inf){
                              pos[s + 1].pb(adj[x][y][d]);
                         }
                    }
                    pos[s].clear();
               }
          }
     }
 
     int ans = inf;
     rep(i,0,n) rep(j,0,m) ans = min(ans, dist[vl[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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 207 ms 56196 KB Output is correct
12 Correct 13 ms 8020 KB Output is correct
13 Correct 92 ms 36964 KB Output is correct
14 Correct 254 ms 59604 KB Output is correct
15 Correct 166 ms 52040 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 207 ms 56196 KB Output is correct
12 Correct 13 ms 8020 KB Output is correct
13 Correct 92 ms 36964 KB Output is correct
14 Correct 254 ms 59604 KB Output is correct
15 Correct 166 ms 52040 KB Output is correct
16 Correct 452 ms 107244 KB Output is correct
17 Correct 738 ms 138760 KB Output is correct
18 Correct 444 ms 111764 KB Output is correct
19 Correct 432 ms 107580 KB Output is correct
20 Correct 561 ms 129764 KB Output is correct