Submission #1049030

#TimeUsernameProblemLanguageResultExecution timeMemory
1049030adiyerRobots (APIO13_robots)C++17
30 / 100
1538 ms81164 KiB
// #pragma optimize ("g",on) // #pragma GCC optimize("inline") // #pragma GCC optimize ("Ofast") // #pragma GCC optimize ("unroll-loops") // #pragma GCC optimize ("03") // #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native") #include <bits/stdc++.h> #define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout); #define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0); #define bitcount(n) __builtin_popcountll(n) #define puts(x) (x ? "YES\n" : "NO\n"); #define ent (i == n ? '\n' : ' ') #define all(x) x.begin(), x.end() #define md ((l + r) >> 1) #define rv(v) ((v << 1) | 1) #define lv(v) (v << 1) #define rs(v) rv(v), md + 1, r #define ls(v) lv(v), l, md #define len(s) (int) s.size() #define pb push_back #define S second #define F first // #define int long long using namespace std; typedef int ll; typedef long double ld; typedef vector < ll > vll; typedef pair < ll, ll > pll; typedef vector < pair < ll, ll > > vpll; const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}; const int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1}; const int N = 5e2 + 2; const int K = 2e5; const int mod = 998244353; const ll inf = 1e9 + 10; //mt19937 rnd(07062006); ll k, n, m, res, cur, cnt; ll ans[51][N][N], seg[10][10]; pll was[N][N][4]; bool vis[N][N][4]; char a[N][N]; queue < pll > q; pll dfs(ll x, ll y, ll di){ pll &w = was[x][y][di]; if(was[x][y][di].F) return w; if(vis[x][y][di]) return w = {-1, -1}; vis[x][y][di] = 1; if(a[x][y] == 'A') di = (di + 1) % 4; if(a[x][y] == 'C') di = (di + 3) % 4; ll nx = x + dx[di], ny = y + dy[di]; if(nx >= 1 && ny >= 1 && nx <= n && ny <= m && a[nx][ny] != 'x') return w = dfs(nx, ny, di); else return w = {x, y}; } inline void bfs(pll s, ll id){ for(ll i = 1; i <= n; i++) for(ll j = 1; j <= m; j++) ans[seg[id][id]][i][j] = inf; q.push(s), ans[seg[id][id]][s.F][s.S] = 0; while(len(q)){ auto [x, y] = q.front(); q.pop(); for(ll i = 0; i < 4; i++){ auto [nx, ny] = was[x][y][i]; if(nx == -1 || ans[seg[id][id]][nx][ny] != inf) continue; ans[seg[id][id]][nx][ny] = ans[seg[id][id]][x][y] + 1; q.push({nx, ny}); } } } vll v; vpll pos[N * N * 10]; ll num; void output(){ cin >> k >> m >> n, res = inf; for(ll i = 1; i <= k; i++) for(ll j = i; j <= k; j++) seg[i][j] = ++num; for(ll i = 1; i <= n; i++) for(ll j = 1; j <= m; j++) cin >> a[i][j]; for(ll i = 1; i <= n; i++) for(ll j = 1; j <= m; j++) for(ll di = 0; di < 4; di++) dfs(i, j, di); for(ll i = 1; i <= n; i++) for(ll j = 1; j <= m; j++) if('1' <= a[i][j] && a[i][j] <= '9') bfs({i, j}, a[i][j] - '0'); for(ll sz = 2; sz <= k; sz++){ for(ll l = 1; l + sz - 1 <= k; l++){ ll r = l + sz - 1; pair < ll, pll > mn = {inf, {inf, inf}}; for(ll i = 1; i <= n; i++){ for(ll j = 1; j <= m; j++){ ans[seg[l][r]][i][j] = inf; for(ll id = l; id < r; id++) ans[seg[l][r]][i][j] = min(ans[seg[l][r]][i][j], ans[seg[l][id]][i][j] + ans[seg[id + 1][r]][i][j]); if(ans[seg[l][r]][i][j] < inf){ v.pb(ans[seg[l][r]][i][j]); pos[ans[seg[l][r]][i][j]].pb({i, j}); mn = min(mn, {ans[seg[l][r]][i][j], {i, j}}); } } } if(mn.F == inf) continue; for(auto x : pos[mn.F]) q.push(x); pos[mn.F].clear(); while(!q.empty()){ auto [x, y] = q.front(); q.pop(); ll cst = ans[seg[l][r]][x][y]; if(len(pos[cst + 1])){ for(auto it : pos[cst + 1]) if(ans[seg[l][r]][it.F][it.S] > cst) q.push(it); pos[cst + 1].clear(); } for(ll di = 0; di < 4; di++){ auto [nx, ny] = was[x][y][di]; if(nx == -1 || ans[seg[l][r]][nx][ny] <= cst) continue; ans[seg[l][r]][nx][ny] = cst + 1; q.push({nx, ny}); } } for(auto it : v) pos[it].clear(); v.clear(); } } for(ll i = 1; i <= n; i++) for(ll j = 1; j <= m; j++) res = min(res, ans[seg[1][k]][i][j]); if(res == inf) res = -1; cout << res; } const bool cases = 0; signed main(){ // file("disrupt"); adiyer(); int tt = 1; if(cases) cin >> tt; for(int i = 1; i <= tt; i++){ output(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...