oj.uz

Submission #918074

# Submission time Handle Problem Language Result Execution time Memory
918074 2024-01-29T13:04:40 Z Boycl07 Robots (APIO13_robots) C++17
100 / 100
 1177 ms 143104 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task "note"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}


const int N =  500 + 10;
const int M = 1e3 + 3;
const int N1 = 2e3 + 10;
const int K = 1e2 + 1;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LINF = 1e17 + 2;
const int block_size = 500;
const int LOG = 29;
const int offset = N;
const int LIM = 11 ;
const int AL = 26;

int n, w, h;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

char a[N][N];
int idx[N][N];

vector<int> adj[N * N];

int dp[LIM][LIM][N * N];

bool in(int x, int y)
{
    return x >= 1 && y >= 1 && x <= h && y <= w && a[x][y] != 'x';
}

void solve()
{
    cin >> n >> w >> h;
    int cnt = 0;
    rep(i, h) rep(j, w)
    {
        cin >> a[i][j]; cnt += a[i][j] != 'x';
        idx[i][j] = cnt;
    }

    rep(i, h) rep(j, w)
        if(in(i, j))
        {
            forn(d, 0, 3)
            if(!in(i + dx[d], j + dy[d]))
            {
                int cur = d;
                int x = i, y = j;

                while(in(x, y))
                {
                    adj[idx[x][y]].pb(idx[i][j]);
                    if(a[x][y] == 'A') cur = (cur + 1) & 3;
                    else if(a[x][y] == 'C') cur = (cur + 3) & 3;
                    x -= dx[cur]; y -= dy[cur];
                }

            }
        }
    memset(dp, 0x3f, sizeof dp);
    rep(i, h) rep(j, w) if(a[i][j] >= '1' && a[i][j] <= '9')
    {
        dp[a[i][j] - '0'][a[i][j] - '0'][idx[i][j]] = 0;
    }
    ford(l, n, 1) forn(r, l, n)
    {
        vector<pii> dist;
        forn(idx, 1, cnt)
        {
            forn(k, l, r - 1)
                minimize(dp[l][r][idx], dp[l][k][idx] + dp[k + 1][r][idx]);
            dist.pb({dp[l][r][idx], idx});
        }
        sort(all(dist));

        vector<int> q, q_;

        int j = 0;

        while(!q.empty() || j < sz(dist))
        {
            if(q.empty())
            {
                if(dp[l][r][dist[j].se] == dist[j].fi) q.pb(dist[j++].se);
                else
                {
                    ++j; continue;
                }
            }

            while(j < sz(dist) && dp[l][r][dist[j].se] == dp[l][r][q.back()])
                q.push_back(dist[j].se), ++j;
            q_.clear();
            while(!q.empty())
            {
                int u = q.back(); q.pop_back();
                for(int v : adj[u]) if(minimize(dp[l][r][v], dp[l][r][u] + 1))
                    q_.pb(v);
            }
            q = move(q_);
        }
    }

    int res = INF;
    rep(i, cnt) minimize(res, dp[1][n][i]);

    if(res == INF) cout << -1;
    else cout << res;

}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int TC = 1;

    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }


    while(TC--)
    {
        solve();
        cout << endl;
    }

    return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 129872 KB Output is correct
2 Correct 22 ms 129884 KB Output is correct
3 Correct 21 ms 129884 KB Output is correct
4 Correct 22 ms 129884 KB Output is correct
5 Correct 24 ms 130128 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 129872 KB Output is correct
2 Correct 22 ms 129884 KB Output is correct
3 Correct 21 ms 129884 KB Output is correct
4 Correct 22 ms 129884 KB Output is correct
5 Correct 24 ms 130128 KB Output is correct
6 Correct 23 ms 129872 KB Output is correct
7 Correct 23 ms 129892 KB Output is correct
8 Correct 22 ms 129884 KB Output is correct
9 Correct 23 ms 129880 KB Output is correct
10 Correct 22 ms 129884 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 129872 KB Output is correct
2 Correct 22 ms 129884 KB Output is correct
3 Correct 21 ms 129884 KB Output is correct
4 Correct 22 ms 129884 KB Output is correct
5 Correct 24 ms 130128 KB Output is correct
6 Correct 23 ms 129872 KB Output is correct
7 Correct 23 ms 129892 KB Output is correct
8 Correct 22 ms 129884 KB Output is correct
9 Correct 23 ms 129880 KB Output is correct
10 Correct 22 ms 129884 KB Output is correct
11 Correct 158 ms 132780 KB Output is correct
12 Correct 32 ms 132412 KB Output is correct
13 Correct 168 ms 132876 KB Output is correct
14 Correct 194 ms 132788 KB Output is correct
15 Correct 127 ms 132796 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 129872 KB Output is correct
2 Correct 22 ms 129884 KB Output is correct
3 Correct 21 ms 129884 KB Output is correct
4 Correct 22 ms 129884 KB Output is correct
5 Correct 24 ms 130128 KB Output is correct
6 Correct 23 ms 129872 KB Output is correct
7 Correct 23 ms 129892 KB Output is correct
8 Correct 22 ms 129884 KB Output is correct
9 Correct 23 ms 129880 KB Output is correct
10 Correct 22 ms 129884 KB Output is correct
11 Correct 158 ms 132780 KB Output is correct
12 Correct 32 ms 132412 KB Output is correct
13 Correct 168 ms 132876 KB Output is correct
14 Correct 194 ms 132788 KB Output is correct
15 Correct 127 ms 132796 KB Output is correct
16 Correct 1177 ms 143104 KB Output is correct
17 Correct 588 ms 137352 KB Output is correct
18 Correct 322 ms 137092 KB Output is correct
19 Correct 719 ms 137356 KB Output is correct
20 Correct 483 ms 137284 KB Output is correct