oj.uz

Submission #1111072

# Submission time Handle Problem Language Result Execution time Memory
1111072 2024-11-11T12:05:12 Z dosts Robots (APIO13_robots) C++17
10 / 100
 1 ms 504 KB 
//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
#define ps(xxx) cout << (xxx) << endl;
const int N = 5e2+1,inf = 1e18,MOD = 1e9+7; 

char grid[501][501];
vector<pii> dirs = {{0,1},{1,0},{0,-1},{-1,0}};
vector<char> chs = {'R','D','L','U'};
int H,W;
struct Graph {
    int nd = 0;
    vector<vi> g;
    vector<pii> nds;
    map<pii,int> nodes;
    vi vals;
    void setval(int id,int v) {
        vals[id] = v;
    }

    void spread() {
        priority_queue<pii,vector<pii>,greater<pii>> pq;
        for (int i=0;i<nd;i++) pq.push({vals[i],i});
        while (!pq.empty()) {
            pii f = pq.top();
            pq.pop();
            if (vals[f.ss] < f.ff) continue;
            for (auto it : g[f.ss]) {
                if (vals[it] > vals[f.ss]+1) {
                    vals[it] = vals[f.ss]+1;
                    pq.push({vals[it],it});
                }
            }
        }
    }
    bool cool(int r,int c) {
        return (r>=0 && r < H && c >= 0 && c < W && grid[r][c]!='x');
    }
    int id(int r,int c) {
        if (!nodes.count({r,c})) return -1;
        return nodes[{r,c}];
    }
    void newnode(int r,int c) {
        if (id(r,c) != -1) return;
        g.push_back({});
        nodes[{r,c}] = nd++;
        nds.push_back({r,c});
        vals.push_back(inf);
        dfs(r,c);
    }
    pii get(int id) {
        return nds[id];
    }
    void addedge(int a,int b) {
        assert(a <= nd && b <= nd);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    void simulate(int r,int c,int dir,int rootid,int rootdir,bool fl = 0) {
        if (grid[r][c] == 'C') dir = (dir+1)%4;
        if (grid[r][c] == 'A') dir = (dir+3)%4;
        if (id(r,c) == rootid && dir == rootdir && fl) {
            cout << -1 << '\n';
            exit(0);
        }
        if (!cool(r+dirs[dir].ff,c+dirs[dir].ss)) {
            if (!cool(r+dirs[dir].ff,c+dirs[dir].ss)) {
                newnode(r,c);
                if (id(r,c) != rootid) addedge(rootid,id(r,c));
            }
            return;
        }
        else {
            r = r+dirs[dir].ff;
            c = c+dirs[dir].ss;
            simulate(r,c,dir,rootid,rootdir,1);
        }
    }
    void dfs(int r,int c) {
        for (int i=0;i<4;i++) simulate(r,c,i,id(r,c),i,0);
    }
};
void solve() { 
    int n;
    cin >> n >> W >> H;
    Graph G;
    for (int i=0;i<H;i++) {
        string s;
        cin >> s;
        for (int j = 0;j<W;j++) grid[i][j] = s[j];
    }
    for (int i=0;i<H;i++) {
        for (int j = 0;j<W;j++) {
            if (grid[i][j] >= '1' && grid[i][j] <= '9') G.newnode(i,j);
        }
    }
    int node = G.nd;
    int dp[node][n+1][n+1];
    for (int i=0;i<node;i++) {
        for (int L = 1;L<=n;L++) {
            for (int R = 1;R<=n;R++) dp[i][L][R] = inf;
        }
    }
    for (int L = n;L>=1;L--) {
        for (int R = L;R<=n;R++) {
            for (int i = 0;i<node;i++) {
                for (int M = L;M<R;M++) dp[i][L][R] = min(dp[i][L][R],dp[i][L][M]+dp[i][M+1][R]);
                int r = G.get(i).ff,c = G.get(i).ss;
                if (L == R && grid[r][c] == L+'0') dp[i][L][R] = 0;
            }
            for (int i=0;i<node;i++) G.setval(i,dp[i][L][R]);
            G.spread();
            for (int i = 0;i<node;i++) {
                dp[i][L][R] = G.vals[i]; 
                //cout << G.get(i).ff sp G.get(i).ss sp L sp R sp dp[i][L][R] << '\n';
            }
        }
    }
    int ans = inf;
    for (int i=0;i<node;i++) ans = min(ans,dp[i][1][n]);
    if (ans < inf) cout << ans << endl;
    else cout << -1 << endl;
}  
 
                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 1 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 1 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 1 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -