Submission #1180302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180302		Gray	Robots (APIO13_robots)	C++20	30 / 100	1595 ms	17812 KiB

robots

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

void solve(){
    ll n, w, h; cin >> n >> w >> h;
    vector<vector<ll>> gr(h, vector<ll>(w));
    vector<pair<ll, ll>> pos(n);
    for (ll i=0; i<h; i++){
        for (ll j=0; j<w; j++){
            char x; cin >> x;
            if (x=='A'){
                gr[i][j]=-1;
            }else if (x=='C'){
                gr[i][j]=-2;
            }else if (x=='x'){
                gr[i][j]=-3;
            }else if (x!='.'){
                gr[i][j]=x-'0';
                pos[x-'0'-1]={i, j};
            }
        }
    }
    // U-0, L-1, D-2, R-3

    vector<pair<ll, ll>> mvs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    vector<vector<vector<pair<ll, ll>>>> path(h, vector<vector<pair<ll, ll>>>(w, vector<pair<ll, ll>>(4, {-1, -1})));
    set<pair<ll, ll>> vis;
    for (ll i=0; i<h; i++){
        for (ll j=0; j<w; j++){
            for (ll dir=0; dir<4; dir++){
                vis.clear();
                pair<ll, ll> cur = {i, j};
                ll cdir = (dir+(gr[i][j]==-1?1:gr[i][j]==-2?-1:0)+4)%4;
                while (cur.ff+mvs[cdir].ff>=0 and cur.ff+mvs[cdir].ff<h and cur.ss+mvs[cdir].ss>=0 and cur.ss+mvs[cdir].ss<w and gr[cur.ff+mvs[cdir].ff][cur.ss+mvs[cdir].ss]!=-3){
                    // cout << i << " - " << j << " = " << dir << " <-> " << cur.ff << " - " << cur.ss << " : " << cdir << endl;
                    vis.insert(cur);
                    cur.ff+=mvs[cdir].ff; cur.ss+=mvs[cdir].ss;
                    if (path[cur.ff][cur.ss][cdir].ff!=-1){
                        cur = path[cur.ff][cur.ss][cdir];
                        break;
                    }
                    // cout << cur.ff << " - " << cur.ss << endl;
                    if (vis.count(cur)){
                        cur = {-2, -2};
                        break;
                    }
                    if (gr[cur.ff][cur.ss]==-2){
                        cdir = (cdir-1+4)%4;
                    }else if (gr[cur.ff][cur.ss]==-1){
                        cdir = (cdir+1)%4;
                    }
                }
                if (cur!=mp(i, j)) path[i][j][dir]=cur;
                // cout << i << "-" << j << "-" << dir << " -> " << cur.ff << " " << cur.ss << endl;
            }
        }
    }
    // return;
    vector cost(h, vector(w, set<pair<pair<ll, ll>, ll>>()));
    vector calced(h, vector<ll>(w, 0));
    vector<vector<vector<pair<ll, ll>>>> reachable(h, vector<vector<pair<ll, ll>>>(w));
    priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>>> que;
    auto precalc = [&](ll si, ll sj){
        que.push({0, {si, sj}});
        while (!que.empty()){
            ll c; pair<ll, ll> cur; tie(c, cur) = que.top(); que.pop();
            auto iter = cost[si][sj].lower_bound({cur, -1});
            if (iter!=cost[si][sj].end() and (*iter).ff==cur) continue;
            cost[si][sj].insert({cur, c});
            reachable[si][sj].push_back(cur);
            for (ll i=0; i<4; i++){
                iter = cost[si][sj].lower_bound({path[cur.ff][cur.ss][i], -1});
                if (path[cur.ff][cur.ss][i].ff>=0 and (iter==cost[si][sj].end() or (*iter).ff!=path[cur.ff][cur.ss][i])){
                    que.push({c+1, path[cur.ff][cur.ss][i]});
                }
            }
        }
        sort(reachable[si][sj].begin(), reachable[si][sj].end());
    };
    auto dist = [&](ll si, ll sj, ll ti, ll tj) -> ll{
        if (!calced[si][sj]){
            precalc(si, sj);
        }
        auto iter = cost[si][sj].lower_bound({{ti, tj}, -1});
        return (((iter!=cost[si][sj].end() and (*iter).ff==mp(ti, tj))?(*iter).ss:-1));
    };
    vector dp(n, vector(n, map<ll, map<ll, ll>>()));
    for (ll i=0; i<n; i++){
        dp[i][i][pos[i].ff][pos[i].ss]=0;
    }
    // cout << n << ln;
    // return;
    for (ll len=1; len<n; len++){
        for (ll i=0; i+len<n; i++){
            ll l=i, r=i+len;
            for (ll j=l; j<r; j++){
                ll m = j;
                for (auto &[x1, ys1]:dp[l][m]){
                    for (auto &[y1, c1]:ys1){
                        for (auto &[x2, ys2]:dp[m+1][r]){
                            for (auto &[y2, c2]:ys2){
                                if (!calced[x1][y1]) precalc(x1, y1);
                                if (!calced[x2][y2]) precalc(x2, y2);
                                for (auto [mx, my]:reachable[x1][y1]){
                                    ll pind = lower_bound(reachable[x2][y2].begin(), reachable[x2][y2].end(), mp(mx, my))-reachable[x2][y2].begin();
                                    if (pind==(ll)reachable[x2][y2].size() or reachable[x2][y2][pind]!=mp(mx, my)) continue;
                                    if (!dp[l][r].count(mx) or !dp[l][r][mx].count(my)) dp[l][r][mx][my]=c1+c2+dist(x1, y1, mx, my)+dist(x2, y2, mx, my);
                                    else dp[l][r][mx][my] = min(dp[l][r][mx][my], c1+c2+dist(x1, y1, mx, my)+dist(x2, y2, mx, my));
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    ll ans=INF;
    for (auto &[posx, posys]:dp[0][n-1]){
        for (auto &[posy, c]:posys){
            ans=min(ans, c);
        }
    }
    cout << (ans==INF?-1:ans) << ln;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40