oj.uz

답안 #666781

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
666781 2022-11-29T17:00:10 Z AmirH 로봇 (APIO13_robots) C++14
100 / 100
 876 ms 148172 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];
// dir : chap = 0, rast = 1, paiin = 2, bala = 3
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));
                   // s.insert({dp[get(i, j)][l][r], 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:94:1: warning: control reaches end of non-void function [-Wreturn-type]
   94 | }
      | ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 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 8 ms 14012 KB Output is correct
5 Correct 7 ms 14036 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 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 8 ms 14012 KB Output is correct
5 Correct 7 ms 14036 KB Output is correct
6 Correct 8 ms 13928 KB Output is correct
7 Correct 8 ms 13908 KB Output is correct
8 Correct 7 ms 13908 KB Output is correct
9 Correct 8 ms 13908 KB Output is correct
10 Correct 9 ms 14036 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 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 8 ms 14012 KB Output is correct
5 Correct 7 ms 14036 KB Output is correct
6 Correct 8 ms 13928 KB Output is correct
7 Correct 8 ms 13908 KB Output is correct
8 Correct 7 ms 13908 KB Output is correct
9 Correct 8 ms 13908 KB Output is correct
10 Correct 9 ms 14036 KB Output is correct
11 Correct 189 ms 53876 KB Output is correct
12 Correct 50 ms 51276 KB Output is correct
13 Correct 94 ms 63804 KB Output is correct
14 Correct 284 ms 60240 KB Output is correct
15 Correct 151 ms 52044 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 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 8 ms 14012 KB Output is correct
5 Correct 7 ms 14036 KB Output is correct
6 Correct 8 ms 13928 KB Output is correct
7 Correct 8 ms 13908 KB Output is correct
8 Correct 7 ms 13908 KB Output is correct
9 Correct 8 ms 13908 KB Output is correct
10 Correct 9 ms 14036 KB Output is correct
11 Correct 189 ms 53876 KB Output is correct
12 Correct 50 ms 51276 KB Output is correct
13 Correct 94 ms 63804 KB Output is correct
14 Correct 284 ms 60240 KB Output is correct
15 Correct 151 ms 52044 KB Output is correct
16 Correct 392 ms 140548 KB Output is correct
17 Correct 876 ms 143952 KB Output is correct
18 Correct 374 ms 117644 KB Output is correct
19 Correct 355 ms 148172 KB Output is correct
20 Correct 576 ms 123400 KB Output is correct