oj.uz

Submission #969953

# Submission time Handle Problem Language Result Execution time Memory
969953 2024-04-26T01:50:07 Z steveonalex Robots (APIO13_robots) C++17
100 / 100
 491 ms 113648 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }
 
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
 
const int N = 505, K = 9, INF = 1e9 + 69;
 
enum GridObj{none=0, obstacle=1, anti_clockwise=2, clockwise=3};
 
int n, w, h;
int dp[K][K][N][N];
GridObj grid[N][N];

pair<short, short> graph[N][N][4];
int num[N][N][4];


void dfs(short i, short j, short x){
    array<short, 3> u = {{i, j, x}};

    if (num[u[0]][u[1]][u[2]] == 1) {
        graph[u[0]][u[1]][u[2]] = {-1, -1};
        return;
    }
    num[u[0]][u[1]][u[2]] = 1;
    
    array<short, 3> v = {{u[0] + dx[u[2]], u[1]+ dy[u[2]], u[2]}};
    if (grid[v[0]][v[1]] == anti_clockwise) v[2] = (v[2] + 1) % 4;
    else if (grid[v[0]][v[1]] == clockwise) v[2] = (v[2] + 3) % 4;

    if (grid[v[0]][v[1]] == obstacle){
        graph[u[0]][u[1]][u[2]] = {u[0], u[1]};
    }
    else {
        dfs(v[0], v[1], v[2]);
        graph[u[0]][u[1]][u[2]] = graph[v[0]][v[1]][v[2]];
    }
    num[u[0]][u[1]][u[2]] = 2;
}
 
 
pair<int, int> pos[K];

bool visited[N][N];
 
vector<pair<short, short>> q[N * N];
 
void dijkstra(int l, int r){
    memset(visited, 0, sizeof visited);
    int cnt = 0;
    if (l < r){
        for(int mid = l; mid < r; ++mid){
            for(int i = 1; i<=w; ++i) for(int j = 1;j <=h; ++j) 
                minimize(dp[l][r-l][i][j], dp[l][mid-l][i][j] + dp[mid+ 1][r-mid-1][i][j]);
        }
    }
    for(short i = 1; i<=w; ++i) for(short j = 1;j <=h; ++j) if (dp[l][r-l][i][j] < INF) {
        q[dp[l][r-l][i][j]].push_back({i, j});
        cnt++;
    }
 
    for(int distance = 0; cnt > 0; ++distance){
        while(q[distance].size()){
            pair<short, short> u = q[distance].back(); q[distance].pop_back();
            cnt--;
 
            // cout << distance << " "; printArr(u); cout.flush();
 
            if (visited[u.first][u.second]) continue;
            visited[u.first][u.second] = true;
            
            for(int x= 0; x < 4; ++x){
                pair<short, short> v = graph[u.first][u.second][x];
                if (v.first != -1) {
                    if (minimize(dp[l][r-l][v.first][v.second], distance + 1)) {
                        q[distance + 1].push_back(v);
                        cnt++;
                    }
                }
            }
        }
    }
 
    // for(int i = 1; i<=w; ++i) {
    //     for(int j = 1; j<=h; ++j) cout << dp[l][r-l][i][j] << " ";
    //     cout << "\n";
    // }
    // cout << "\n";
}

 
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    cin >> n >> w >> h;
    swap(w, h);
    if (n == 1){
        cout << 0 << "\n";
        return 0;
    }
    for(int i = 0; i<=w+1; ++i) 
    for(int j = 0; j<=h+1; ++j) grid[i][j] = obstacle;
    for(int i = 0; i<w; ++i){
        string s; cin >> s;
        for(int j = 0; j<h; ++j){
            if (s[j] == '.') grid[i+1][j+1]=none;
            else if (s[j] == 'x') grid[i+1][j+1] = obstacle;
            else if (s[j] == 'A') grid[i+1][j+1] = anti_clockwise;
            else if (s[j] == 'C') grid[i+1][j+1] = clockwise;
            else {
                grid[i+1][j+1]=none;
                pos[s[j] - '0' - 1] = {i + 1, j + 1};
            }
        }
    }

    for(int i = 1; i<=w; ++i) for(int j = 1; j<=h; ++j) if (grid[i][j] != obstacle){
        for(int x = 0; x < 4; ++x) if (!num[i][j][x]){
            dfs(i, j, x);
        }
    }
 
    memset(dp, 63, sizeof dp);
 
    for(int i = 0; i<n; ++i){
        dp[i][0][pos[i].first][pos[i].second] = 0;
    }
 
    for(int i = n-1; i>=0; --i)
    for(int j = i; j<n; ++j){
        dijkstra(i, j);
    }
    
    int ans = INF;
    for(int i = 1; i<=w; ++i) for(int j = 1; j<=w; ++j) 
        minimize(ans, dp[0][n-1][i][j]);
 
    if (ans == INF) ans = -1;
    cout << ans << "\n";
 
 
    return 0;
}

Compilation message

robots.cpp: In function 'void dfs(short int, short int, short int)':
robots.cpp:70:32: warning: narrowing conversion of '(((int)u.std::array<short int, 3>::operator[](0)) + dx[((int)u.std::array<short int, 3>::operator[](2))])' from 'int' to 'short int' [-Wnarrowing]
   70 |     array<short, 3> v = {{u[0] + dx[u[2]], u[1]+ dy[u[2]], u[2]}};
robots.cpp:70:48: warning: narrowing conversion of '(((int)u.std::array<short int, 3>::operator[](1)) + dy[((int)u.std::array<short int, 3>::operator[](2))])' from 'int' to 'short int' [-Wnarrowing]
   70 |     array<short, 3> v = {{u[0] + dx[u[2]], u[1]+ dy[u[2]], u[2]}};

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 92252 KB Output is correct
2 Correct 13 ms 92252 KB Output is correct
3 Correct 13 ms 92252 KB Output is correct
4 Correct 13 ms 92340 KB Output is correct
5 Correct 13 ms 92248 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 92252 KB Output is correct
2 Correct 13 ms 92252 KB Output is correct
3 Correct 13 ms 92252 KB Output is correct
4 Correct 13 ms 92340 KB Output is correct
5 Correct 13 ms 92248 KB Output is correct
6 Correct 13 ms 92252 KB Output is correct
7 Correct 13 ms 92412 KB Output is correct
8 Correct 13 ms 92504 KB Output is correct
9 Correct 14 ms 92248 KB Output is correct
10 Correct 13 ms 92252 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 92252 KB Output is correct
2 Correct 13 ms 92252 KB Output is correct
3 Correct 13 ms 92252 KB Output is correct
4 Correct 13 ms 92340 KB Output is correct
5 Correct 13 ms 92248 KB Output is correct
6 Correct 13 ms 92252 KB Output is correct
7 Correct 13 ms 92412 KB Output is correct
8 Correct 13 ms 92504 KB Output is correct
9 Correct 14 ms 92248 KB Output is correct
10 Correct 13 ms 92252 KB Output is correct
11 Correct 49 ms 98904 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 85 ms 94792 KB Output is correct
14 Correct 83 ms 101204 KB Output is correct
15 Correct 41 ms 97120 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 92252 KB Output is correct
2 Correct 13 ms 92252 KB Output is correct
3 Correct 13 ms 92252 KB Output is correct
4 Correct 13 ms 92340 KB Output is correct
5 Correct 13 ms 92248 KB Output is correct
6 Correct 13 ms 92252 KB Output is correct
7 Correct 13 ms 92412 KB Output is correct
8 Correct 13 ms 92504 KB Output is correct
9 Correct 14 ms 92248 KB Output is correct
10 Correct 13 ms 92252 KB Output is correct
11 Correct 49 ms 98904 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 85 ms 94792 KB Output is correct
14 Correct 83 ms 101204 KB Output is correct
15 Correct 41 ms 97120 KB Output is correct
16 Correct 491 ms 96416 KB Output is correct
17 Correct 200 ms 113648 KB Output is correct
18 Correct 64 ms 99412 KB Output is correct
19 Correct 336 ms 96408 KB Output is correct
20 Correct 133 ms 104912 KB Output is correct