oj.uz

Submission #666782

# Submission time Handle Problem Language Result Execution time Memory
666782 2022-11-29T17:06:50 Z AmirH Robots (APIO13_robots) C++14
100 / 100
 843 ms 147828 KB 
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<bitset>
#include<queue>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<unordered_map>
#include<list>
#include<utility>
#include<stack>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
#define cl clear
#define F  first
#define S  second
#define pb push_back
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define faster ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const int MAX_N = 5e2 + 10;
const ll INF = 1e18;
const int inf = 1e9;
void free() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}
int n, w, h;
char ch[MAX_N][MAX_N];
set<int> sat[MAX_N], sot[MAX_N];
set<int> satan[MAX_N], sotan[MAX_N];
vector<int> adj[MAX_N * MAX_N];
int heightst[MAX_N * MAX_N][10];
int rast[MAX_N * MAX_N], chap[MAX_N * MAX_N], bala[MAX_N * MAX_N], paiin[MAX_N * MAX_N];
bool check[MAX_N][MAX_N][5];
int final_ex[MAX_N][MAX_N][5];
int dp[MAX_N * MAX_N][10][10];
vector<int> vtx[MAX_N * MAX_N];
int get(int x, int y) {
    return (x - 1) * w + y;
}
int find_ex(int x, int y, int dir) {
    if(final_ex[x][y][dir] != 0)
        return final_ex[x][y][dir];
    if(check[x][y][dir])
        return 0;
    check[x][y][dir] = 1;
    int st;
    if(dir == 0) {
        st = *(--sat[x].lower_bound(y));
        if(ch[x][st] == 'x')
            return final_ex[x][y][dir] = get(x, st + 1);
        else if(ch[x][st] == 'A')
           return final_ex[x][y][dir] = find_ex(x, st, 2);
        else
           return final_ex[x][y][dir] = find_ex(x, st, 3);
    }
    if(dir == 1) {
        st = *(sat[x].upper_bound(y));
        if(ch[x][st] == 'x')
            return final_ex[x][y][dir] = get(x, st - 1);
        else if(ch[x][st] == 'A') 
            return final_ex[x][y][dir] = find_ex(x, st, 3);
        else
           return final_ex[x][y][dir] = find_ex(x, st, 2);
    }
    if(dir == 2) {
        st = *(sot[y].upper_bound(x));
        if(ch[st][y] == 'x')
            return final_ex[x][y][dir] = get(st - 1, y);
        else if(ch[st][y] == 'A')
            return final_ex[x][y][dir] = find_ex(st, y, 1);
        else
            return final_ex[x][y][dir] = find_ex(st, y, 0);
    }
    if(dir == 3) {
        st = *(--sot[y].lower_bound(x));
        if(ch[st][y] == 'x')
            return final_ex[x][y][dir] = get(st + 1, y);
        else if(ch[st][y] == 'A')
            return final_ex[x][y][dir] = find_ex(st, y, 0);
        else
            return final_ex[x][y][dir] = find_ex(st, y, 1);
    }
}

void bfs(int st, int d) {
    int height[MAX_N * MAX_N];
    bool mark[MAX_N * MAX_N];
    for(int i = 1; i <= h * w; i++)
        height[i] = inf, mark[i] = false;
    queue<int> q;
    q.push(st);
    mark[st] = true;
    height[st] = 0;
    while(q.size()) {
        int x = q.front();
        q.pop();
        for(auto i : adj[x])
            if(!mark[i]) {
                mark[i] = true;
                q.push(i);
                height[i] = height[x] + 1;
            }
    }
    for(int i = 1; i <= h * w; i++)
        heightst[i][d] = height[i];
}
void find(int x, int y) {
    int st = get(x, y);
    rast[st] = find_ex(x, y, 1);
    chap[st] = find_ex(x, y, 0);
    bala[st] = find_ex(x, y, 3);
    paiin[st] = find_ex(x, y, 2);
    if(rast[st] != st && rast[st] != 0) {
        adj[st].pb(rast[st]);
    }
    if(chap[st] != st && chap[st] != 0) {
        adj[st].pb(chap[st]);
    }
    if(paiin[st] != st && paiin[st] != 0) {
        adj[st].pb(paiin[st]);
    }
    if(bala[st] != st && bala[st] != 0) {
        adj[st].pb(bala[st]);
    }
}
void setdef() {
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) {
            if(ch[i][j] == 'x')
                continue;
            for(int k = 1; k <= 9; k++) {
                for(int p = 1; p <= 9; p++) {
                    dp[get(i, j)][k][p] = inf;
                }
            }
        }
    }
}

void bfs2(int l, int r) {
    for(int i = 0; i < MAX_N * MAX_N - 5; i++) {
        while(vtx[i].size()) {
            int j = vtx[i].back();
            vtx[i].pop_back();
            if(i == dp[j][l][r]) {
                for(auto k : adj[j]) {
                    if(i + 1 < dp[k][l][r]) {
                        dp[k][l][r] = i + 1;
                        vtx[i + 1].pb(k);
                    }
                }
            }
        }
    }
}
int main() {
    faster; //free();
    cin >> n >> w >> h;
    for(int i = 0; i <= h + 1; i++){
        for(int j = 0; j <= w + 1; j++) {
            if(i == 0 || i == h + 1 || j == 0 || j == w + 1)
                ch[i][j] = 'x';
            else
                cin >> ch[i][j];
            if(ch[i][j] == 'x' || ch[i][j] == 'A' || ch[i][j] == 'C') {
                sat[i].insert(j);
                sot[j].insert(i);
            }
        }
    }
    vector<pair<pii, int>> nodes;
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) {
            if(ch[i][j] == 'x')
                continue;
            find(i, j);
            if(ch[i][j] - '0' >= 1 && ch[i][j] - '0' <= 9)
                nodes.pb({{i, j}, ch[i][j] - '0'});
        }
    }
    for(auto i : nodes) {
        bfs(get(i.first.first, i.first.second), i.second);
    }
    setdef();
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) {
            if(ch[i][j] == 'x')
                continue;
            for(int k = 1; k <= n; k++)
                dp[get(i, j)][k][k] = heightst[get(i, j)][k];
        }
    }
    for(int len = 1; len < n; len++) {
        for(int l = 1; l <= n - len; l++) {
            int r = l + len;
            for(int i = 1; i <= h; i++) {
                for(int j = 1; j <= w; j++) {
                    if(ch[i][j] == 'x')
                        continue;
                    for(int k = l; k < r; k++) {
                        dp[get(i, j)][l][r] = min(dp[get(i, j)][l][k] + dp[get(i, j)][k + 1][r], dp[get(i, j)][l][r]);
                    }
                        if(dp[get(i, j)][l][r] < MAX_N * MAX_N)
                    vtx[dp[get(i, j)][l][r]].pb(get(i, j));
                }
            }
            bfs2(l, r);
        }
    }
    int res = inf;
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) 
            if(ch[i][j] != 'x')
                res = min(res, dp[get(i, j)][1][n]);
    }
    if(res == inf)
        cout << -1;
    else
        cout << res;
}

Compilation message

robots.cpp: In function 'void free()':
robots.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp: In function 'int find_ex(int, int, int)':
robots.cpp:93:1: warning: control reaches end of non-void function [-Wreturn-type]
   93 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13908 KB Output is correct
2 Correct 8 ms 13908 KB Output is correct
3 Correct 8 ms 13908 KB Output is correct
4 Correct 9 ms 14048 KB Output is correct
5 Correct 9 ms 14036 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13908 KB Output is correct
2 Correct 8 ms 13908 KB Output is correct
3 Correct 8 ms 13908 KB Output is correct
4 Correct 9 ms 14048 KB Output is correct
5 Correct 9 ms 14036 KB Output is correct
6 Correct 8 ms 13908 KB Output is correct
7 Correct 8 ms 13908 KB Output is correct
8 Correct 8 ms 13908 KB Output is correct
9 Correct 8 ms 13868 KB Output is correct
10 Correct 9 ms 14036 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13908 KB Output is correct
2 Correct 8 ms 13908 KB Output is correct
3 Correct 8 ms 13908 KB Output is correct
4 Correct 9 ms 14048 KB Output is correct
5 Correct 9 ms 14036 KB Output is correct
6 Correct 8 ms 13908 KB Output is correct
7 Correct 8 ms 13908 KB Output is correct
8 Correct 8 ms 13908 KB Output is correct
9 Correct 8 ms 13868 KB Output is correct
10 Correct 9 ms 14036 KB Output is correct
11 Correct 184 ms 53836 KB Output is correct
12 Correct 51 ms 51200 KB Output is correct
13 Correct 109 ms 63692 KB Output is correct
14 Correct 312 ms 60152 KB Output is correct
15 Correct 144 ms 52052 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13908 KB Output is correct
2 Correct 8 ms 13908 KB Output is correct
3 Correct 8 ms 13908 KB Output is correct
4 Correct 9 ms 14048 KB Output is correct
5 Correct 9 ms 14036 KB Output is correct
6 Correct 8 ms 13908 KB Output is correct
7 Correct 8 ms 13908 KB Output is correct
8 Correct 8 ms 13908 KB Output is correct
9 Correct 8 ms 13868 KB Output is correct
10 Correct 9 ms 14036 KB Output is correct
11 Correct 184 ms 53836 KB Output is correct
12 Correct 51 ms 51200 KB Output is correct
13 Correct 109 ms 63692 KB Output is correct
14 Correct 312 ms 60152 KB Output is correct
15 Correct 144 ms 52052 KB Output is correct
16 Correct 399 ms 140408 KB Output is correct
17 Correct 843 ms 143724 KB Output is correct
18 Correct 372 ms 117380 KB Output is correct
19 Correct 350 ms 147828 KB Output is correct
20 Correct 600 ms 123252 KB Output is correct