oj.uz

Submission #257222

# Submission time Handle Problem Language Result Execution time Memory
257222 2020-08-03T22:46:05 Z aggu_01000101 Robots (APIO13_robots) C++14
60 / 100
 550 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 N = 500005;
string m[505];
int status[505][505][10]; //0->not vis, 1-> calc, 2-> done calc
int dp[505][505][10][10];
pair<int, int> final[505][505][4];
vector<pair<int, int>> adj[505][505];
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(status[i][j][dir] == 2){
        return final[i][j][dir];
    }
    else if(status[i][j][dir]==1){
        return {-1, -1};
    }
    status[i][j][dir] = 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;
        status[i][j][currd] = 2;
        return final[i][j][currd] = {i, j};
    }
    final[i][j][currd] = dfs(togo.first, togo.second, dir);
    status[i][j][currd] = 2;
    //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++){
                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;
            vector<int> allc;
            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});
                        allc.push_back(dp[i][j][st][sd]);
                    }
                }
            }
            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 k: allc) 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 8704 KB Output is correct
2 Correct 5 ms 8704 KB Output is correct
3 Correct 5 ms 8576 KB Output is correct
4 Correct 7 ms 8832 KB Output is correct
5 Correct 5 ms 8832 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8704 KB Output is correct
2 Correct 5 ms 8704 KB Output is correct
3 Correct 5 ms 8576 KB Output is correct
4 Correct 7 ms 8832 KB Output is correct
5 Correct 5 ms 8832 KB Output is correct
6 Correct 6 ms 8704 KB Output is correct
7 Correct 6 ms 8704 KB Output is correct
8 Correct 6 ms 8704 KB Output is correct
9 Correct 7 ms 8704 KB Output is correct
10 Correct 5 ms 8832 KB Output is correct
11 Correct 220 ms 57224 KB Output is correct
12 Correct 40 ms 53368 KB Output is correct
13 Correct 100 ms 56184 KB Output is correct
14 Correct 388 ms 59524 KB Output is correct
15 Correct 151 ms 54680 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8704 KB Output is correct
2 Correct 5 ms 8704 KB Output is correct
3 Correct 5 ms 8576 KB Output is correct
4 Correct 7 ms 8832 KB Output is correct
5 Correct 5 ms 8832 KB Output is correct
6 Correct 6 ms 8704 KB Output is correct
7 Correct 6 ms 8704 KB Output is correct
8 Correct 6 ms 8704 KB Output is correct
9 Correct 7 ms 8704 KB Output is correct
10 Correct 5 ms 8832 KB Output is correct
11 Correct 220 ms 57224 KB Output is correct
12 Correct 40 ms 53368 KB Output is correct
13 Correct 100 ms 56184 KB Output is correct
14 Correct 388 ms 59524 KB Output is correct
15 Correct 151 ms 54680 KB Output is correct
16 Correct 428 ms 137464 KB Output is correct
17 Runtime error 550 ms 163840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -