oj.uz

Submission #257228

# Submission time Handle Problem Language Result Execution time Memory
257228 2020-08-03T22:55:40 Z aggu_01000101 Robots (APIO13_robots) C++14
60 / 100
 548 ms 163840 KB 
#include <iostream>
#include <bits/stdc++.h>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <iomanip>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
//#define int long long
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
using namespace std;
const int H = 501;
string m[H];
int dp[H][H][10][10];
pair<int, int> final[H][H][4];
vector<pair<int, int>> adj[H][H];
int n, h, w;
int A(int x){
    return ((x+1)%4);
}
int C(int x){
    return ((x-1+4)%4);
}
bool valid(pair<int, int> x){
    if(x.first < 0 || x.second<0) return false;
    if(x.first >= h || x.second >= w) return false;
    return m[x.first][x.second] != 'x';
}
pair<int, int> update(pair<int, int> x, int dir){
    if(dir==0){
        x.first++;
        return x;
    }
    if(dir==1){
        x.second++;
        return x;
    }
    if(dir==2){
        x.first--;
        return x;
    }
    x.second--;
    return x;
}
pair<int, int> nxt(pair<int, int> curr, int &dir){
    if(m[curr.first][curr.second]=='C') dir = C(dir);
    else if(m[curr.first][curr.second]=='A') dir = A(dir);
    if(!valid(update(curr, dir))) return curr;
    return update(curr, dir);
}
pair<int, int> dfs(int i, int j, int dir){
    if(final[i][j][dir].first >=0){
        return final[i][j][dir];
    }
    else if(final[i][j][dir].first==-1){
        return {-1, -1};
    }
    final[i][j][dir] = {-1, -1};
    int currd = dir;
    pair<int, int> togo = nxt({i, j}, dir);
    if(togo.first == i && togo.second == j){
        //cout<<i<<" "<<j<<" in direction "<<dir<<" can't move"<<endl;
        return final[i][j][currd] = {i, j};
    }
    final[i][j][currd] = dfs(togo.first, togo.second, dir);
    //cout<<i<<" "<<j<<" in direction "<<currd<<" leads to "<<final[i][j][currd].first<<" "<<final[i][j][currd].second<<endl;
    return final[i][j][currd];
}
void BFS(pair<int, int> curr, int st){
    for(int i =0 ;i<h;i++){
        for(int j = 0;j<w;j++) dp[i][j][st][st] = INF;
    }
    dp[curr.first][curr.second][st][st] = 0;
    queue<pair<int, int>> q;
    q.push(curr);
    while(!q.empty()){
        curr = q.front();
        q.pop();
        for(pair<int, int> k: adj[curr.first][curr.second]){
            if(dp[k.first][k.second][st][st] < INF) continue;
            dp[k.first][k.second][st][st] = dp[curr.first][curr.second][st][st] + 1;
            q.push(k);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>w>>h;
    for(int i =0 ;i<h;i++) cin>>m[i];
    //dir 0 -> i++
    //dir 1 -> j++
    //dir 2 -> i--
    //dir 3 -> j--
    for(int i =0 ;i<h;i++){
        for(int j =0 ;j<w;j++){
            for(int k = 0;k<4;k++) final[i][j][k] = {-2, -2};
        }
    }
    for(int i = 0;i<h;i++){
        for(int j = 0;j<w;j++){
            for(int k = 0;k<4;k++){
                if(m[i][j]=='x') continue;
                pair<int, int> ta = dfs(i, j, k);
                //cout<<i<<" "<<j<<" "<<k<<" leads to ("<<ta.first<<", "<<ta.second<<")"<<endl;
                if(ta.first != -1){
                    adj[i][j].push_back(ta);
                }
            }
        }
    }
    for(int i = 0;i<h;i++){
        for(int j = 0;j<w;j++){
            if(m[i][j]=='A' || m[i][j]=='C' || m[i][j]=='x' || m[i][j]=='.') continue;
            int curr = m[i][j] - '0';
            BFS({i, j}, curr);
        }
    }
    vector<pair<int, int>> dPush[100000];
    for(int sz = 1;sz<n;sz++){
        for(int st = 1;(st+sz)<=n;st++){
            int sd = (st+sz);
            pair<int, int> toPush;
            int minCost = INF;
            for(int i =0 ;i<h;i++){
                for(int j = 0;j<w;j++){
                    dp[i][j][st][sd] = INF;
                    for(int k = st;k<sd;k++) dp[i][j][st][sd] = min(dp[i][j][st][k] + dp[i][j][k+1][sd], dp[i][j][st][sd]);
                    if(dp[i][j][st][sd] < INF){
                        minCost = min(minCost, dp[i][j][st][sd]);
                        dPush[dp[i][j][st][sd]].push_back({i, j});
                    }
                }
            }
            if(minCost == INF) continue;
            queue<pair<int, int>> q;
            for(pair<int, int> j: dPush[minCost]) q.push({j.first, j.second});
            dPush[minCost].clear();
            while(!q.empty()){
                pair<int, int> curr = q.front();
                q.pop();
                int i = curr.first, j = curr.second;
                int cd = dp[i][j][st][sd];
                for(pair<int, int> nxt: dPush[cd+1]){
                    if(dp[nxt.first][nxt.second][st][sd] < (cd+1)) continue;
                    dp[nxt.first][nxt.second][st][sd] = cd + 1;
                    q.push(nxt);
                }
                dPush[cd+1].clear();
                for(pair<int, int> nxt: adj[i][j]){
                    if(dp[nxt.first][nxt.second][st][sd] <= (cd+1)) continue;
                    dp[nxt.first][nxt.second][st][sd] = cd + 1;
                    q.push({nxt.first, nxt.second});
                }
            }
            for(int i =0 ;i<h;i++){
                for(int j = 0;j<w;j++){
                    int k = INF;
                    for(int kk = st;kk<sd;kk++) k = min(dp[i][j][st][kk] + dp[i][j][kk+1][sd], k);
                    if(k<INF) dPush[k].clear();
                }
            }
        }
    }
    int ans = INF;
    for(int i =0 ;i<h;i++){
        for(int j =0;j<w;j++){
            ans = min(ans, dp[i][j][1][n]);
        }
    }
    if(ans >= INF) ans = -1;
    cout<<ans<<endl;
}
/*

4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...

*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8576 KB Output is correct
2 Correct 5 ms 8576 KB Output is correct
3 Correct 5 ms 8576 KB Output is correct
4 Correct 5 ms 8704 KB Output is correct
5 Correct 5 ms 8704 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8576 KB Output is correct
2 Correct 5 ms 8576 KB Output is correct
3 Correct 5 ms 8576 KB Output is correct
4 Correct 5 ms 8704 KB Output is correct
5 Correct 5 ms 8704 KB Output is correct
6 Correct 6 ms 8576 KB Output is correct
7 Correct 5 ms 8576 KB Output is correct
8 Correct 5 ms 8576 KB Output is correct
9 Correct 5 ms 8576 KB Output is correct
10 Correct 5 ms 8704 KB Output is correct
11 Correct 262 ms 53752 KB Output is correct
12 Correct 34 ms 50296 KB Output is correct
13 Correct 117 ms 51320 KB Output is correct
14 Correct 425 ms 56388 KB Output is correct
15 Correct 174 ms 51552 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8576 KB Output is correct
2 Correct 5 ms 8576 KB Output is correct
3 Correct 5 ms 8576 KB Output is correct
4 Correct 5 ms 8704 KB Output is correct
5 Correct 5 ms 8704 KB Output is correct
6 Correct 6 ms 8576 KB Output is correct
7 Correct 5 ms 8576 KB Output is correct
8 Correct 5 ms 8576 KB Output is correct
9 Correct 5 ms 8576 KB Output is correct
10 Correct 5 ms 8704 KB Output is correct
11 Correct 262 ms 53752 KB Output is correct
12 Correct 34 ms 50296 KB Output is correct
13 Correct 117 ms 51320 KB Output is correct
14 Correct 425 ms 56388 KB Output is correct
15 Correct 174 ms 51552 KB Output is correct
16 Correct 548 ms 126200 KB Output is correct
17 Runtime error 538 ms 163840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -