Submission #675316

#	Time	Username	Problem	Language	Result	Execution time	Memory
675316		vjudge1	Portals (BOI14_portals)	C++17	0 / 100	46 ms	64116 KiB

portals

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define ALL(v) (v).begin(), (v).end()
#define popcount(x) __builtin_popcount(x)
#define setp(x) setprecision(x)
#define MASK(x) (1LL << (x))
#define BIT(x, i) ((x) >> (i) & 1)
#define ID(x, y) ((x - 1) * m + y)
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

const int NM = 1e6 + 10;
int n, m, start, target;
char a[NM];
ll dp[NM];
vector<pii> edges[NM];
set<pii> r[1005], c[1005];

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

struct Data {
    int x, y, cost;

    bool inline operator < (const Data &A) const {
        return cost > A.cost;
    }
};

bool check(int x, int y) {
    return (x <= n && x > 0 && y <= m && y > 0 && a[ID(x, y)] != '#');
}
void xuli() {
    priority_queue<Data> pq;

    memset(dp, INF, sizeof dp);
    dp[start] = 0;
    int xstart = start / m + 1, ystart = start % m;
    for(int i = 0; i < 4; i++) {
        int u = xstart + dx[i];
        int v = ystart + dy[i];
        if(!check(u, v)) continue;
        if(minimize(dp[ID(u, v)], 1))
            pq.push({u, v, dp[ID(u, v)]});
    }

    auto it = r[xstart].upper_bound({ystart, INF});
    it--;
    pii cur = *it;
    if(minimize(dp[ID(xstart, cur.fi)], min(ystart - cur.fi, cur.se - ystart) + 1))
        pq.push({xstart, cur.fi, dp[ID(xstart, cur.fi)]});
    if(minimize(dp[ID(xstart, cur.se)], min(ystart - cur.fi, cur.se - ystart) + 1))
        pq.push({xstart, cur.se, dp[ID(xstart, cur.se)]});

    auto it2 = c[ystart].upper_bound({xstart, INF});
    it2--;
    pii cur2 = *it2;
    if(minimize(dp[ID(cur2.fi, ystart)], min(xstart - cur2.fi, cur2.se - xstart) + 1))
        pq.push({cur2.fi, ystart, dp[ID(cur2.fi, ystart)]});
    if(minimize(dp[ID(cur2.se, ystart)], min(xstart - cur2.fi, cur2.se - xstart) + 1))
        pq.push({cur2.se, ystart, dp[ID(cur2.se, ystart)]});

    while(pq.size()) {
        Data u = pq.top();
        pq.pop();

        if(u.cost != dp[ID(u.x, u.y)]) continue;

        int curId = ID(u.x, u.y);
        if(curId == target) break;

        for(int i = 0; i < 4; i++) {
            int x = u.x + dx[i];
            int y = u.y + dy[i];
            if(!check(x, y)) continue;
            if(minimize(dp[ID(x, y)], u.cost + 1)) {
                pq.push({x, y, dp[ID(x, y)]});
            }
        }

        auto tmp = r[u.x].upper_bound({u.y, INF});
        tmp--;
        pii tam = *tmp;
        if(minimize(dp[ID(u.x, tam.fi)], u.cost + min(u.y - tam.fi, tam.se - u.y) + 1)) {
            pq.push({u.x, tam.fi, dp[ID(u.x, tam.fi)]});
        }
        if(minimize(dp[ID(u.x, tam.se)], u.cost + min(u.y - tam.fi, tam.se - u.y) + 1)) {
            pq.push({u.x, tam.se, dp[ID(u.x, tam.se)]});
        }

        auto tmp2 = c[u.y].upper_bound({u.x, INF});
        tmp2--;
        pii tam2 = *tmp2;
        if(minimize(dp[ID(tam2.fi, u.y)], u.cost + min(u.x - tam2.fi, tam2.se - u.x) + 1)) {
            pq.push({tam2.fi, u.y, dp[ID(tam2.fi, u.y)]});
        }
        if(minimize(dp[ID(tam2.se, u.y)], u.cost + min(u.x - tam2.fi, tam2.se - u.x) + 1)) {
            pq.push({tam2.se, u.y, dp[ID(tam2.se, u.y)]});
        }
    }

    int res = INF;
    cout << dp[target];
}
int main()
{
    FastIO
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        r[i].insert({1, m});
        r[i].insert({INF, INF});
    }
    for(int i = 1; i <= m; i++) {
        c[i].insert({1, n});
        c[i].insert({INF, INF});
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char u; cin >> u;
            a[(i - 1) * m + j] = u;
            if(u == 'S') start = (i - 1) * m + j;
            if(u == 'C') target = (i - 1) * m + j;
            if(u == '#') {
                auto it = r[i].upper_bound({j, INF});
                it--;
                pii cur = *it;
                r[i].erase(it);

                if(cur.fi <= j - 1) {
                    int u1 = cur.fi, u2 = j - 1;
                    r[i].insert({cur.fi, j - 1});
                }
                if(cur.se >= j + 1) {
                    int u1 = j + 1, u2 = cur.se;
                    r[i].insert({j + 1, cur.se});
                }

                auto it2 = c[j].upper_bound({i, INF});
                it2--;
                pii tmp = *it2;
                c[j].erase(it2);

                if(tmp.fi <= i - 1) {
                    c[j].insert({tmp.fi, i - 1});
                }
                if(tmp.se >= i + 1) {
                    c[j].insert({i + 1, tmp.se});
                }
            }
        }
    }

    /**
    for(int i = 1; i <= n; i++) {
        for(pii u : c[i]) cout << u.fi << " " << u.se << " | ";
        cout << '\n';
    }
    **/

    xuli();
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'void xuli()':
portals.cpp:3:13: warning: overflow in conversion from 'long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
    3 | #define INF 0x3f3f3f3f3f3f3f3f
      |             ^~~~~~~~~~~~~~~~~~
portals.cpp:47:16: note: in expansion of macro 'INF'
   47 |     memset(dp, INF, sizeof dp);
      |                ^~~
portals.cpp:55:39: warning: narrowing conversion of 'dp[(((u - 1) * m) + v)]' from 'long long int' to 'int' [-Wnarrowing]
   55 |             pq.push({u, v, dp[ID(u, v)]});
      |                            ~~~~~~~~~~~^
portals.cpp:62:55: warning: narrowing conversion of 'dp[(((xstart - 1) * m) + cur.std::pair<int, int>::first)]' from 'long long int' to 'int' [-Wnarrowing]
   62 |         pq.push({xstart, cur.fi, dp[ID(xstart, cur.fi)]});
      |                                  ~~~~~~~~~~~~~~~~~~~~~^
portals.cpp:64:55: warning: narrowing conversion of 'dp[(((xstart - 1) * m) + cur.std::pair<int, int>::second)]' from 'long long int' to 'int' [-Wnarrowing]
   64 |         pq.push({xstart, cur.se, dp[ID(xstart, cur.se)]});
      |                                  ~~~~~~~~~~~~~~~~~~~~~^
portals.cpp:70:57: warning: narrowing conversion of 'dp[(((cur2.std::pair<int, int>::first - 1) * m) + ystart)]' from 'long long int' to 'int' [-Wnarrowing]
   70 |         pq.push({cur2.fi, ystart, dp[ID(cur2.fi, ystart)]});
      |                                   ~~~~~~~~~~~~~~~~~~~~~~^
portals.cpp:72:57: warning: narrowing conversion of 'dp[(((cur2.std::pair<int, int>::second - 1) * m) + ystart)]' from 'long long int' to 'int' [-Wnarrowing]
   72 |         pq.push({cur2.se, ystart, dp[ID(cur2.se, ystart)]});
      |                                   ~~~~~~~~~~~~~~~~~~~~~~^
portals.cpp:88:43: warning: narrowing conversion of 'dp[(((x - 1) * m) + y)]' from 'long long int' to 'int' [-Wnarrowing]
   88 |                 pq.push({x, y, dp[ID(x, y)]});
      |                                ~~~~~~~~~~~^
portals.cpp:96:53: warning: narrowing conversion of 'dp[(((u.Data::x - 1) * m) + tam.std::pair<int, int>::first)]' from 'long long int' to 'int' [-Wnarrowing]
   96 |             pq.push({u.x, tam.fi, dp[ID(u.x, tam.fi)]});
      |                                   ~~~~~~~~~~~~~~~~~~^
portals.cpp:99:53: warning: narrowing conversion of 'dp[(((u.Data::x - 1) * m) + tam.std::pair<int, int>::second)]' from 'long long int' to 'int' [-Wnarrowing]
   99 |             pq.push({u.x, tam.se, dp[ID(u.x, tam.se)]});
      |                                   ~~~~~~~~~~~~~~~~~~^
portals.cpp:106:55: warning: narrowing conversion of 'dp[(((tam2.std::pair<int, int>::first - 1) * m) + u.Data::y)]' from 'long long int' to 'int' [-Wnarrowing]
  106 |             pq.push({tam2.fi, u.y, dp[ID(tam2.fi, u.y)]});
      |                                    ~~~~~~~~~~~~~~~~~~~^
portals.cpp:109:55: warning: narrowing conversion of 'dp[(((tam2.std::pair<int, int>::second - 1) * m) + u.Data::y)]' from 'long long int' to 'int' [-Wnarrowing]
  109 |             pq.push({tam2.se, u.y, dp[ID(tam2.se, u.y)]});
      |                                    ~~~~~~~~~~~~~~~~~~~^
portals.cpp:3:13: warning: overflow in conversion from 'long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
    3 | #define INF 0x3f3f3f3f3f3f3f3f
      |             ^~~~~~~~~~~~~~~~~~
portals.cpp:113:15: note: in expansion of macro 'INF'
  113 |     int res = INF;
      |               ^~~
portals.cpp:113:9: warning: unused variable 'res' [-Wunused-variable]
  113 |     int res = INF;
      |         ^~~
portals.cpp: In function 'int main()':
portals.cpp:143:25: warning: unused variable 'u1' [-Wunused-variable]
  143 |                     int u1 = cur.fi, u2 = j - 1;
      |                         ^~
portals.cpp:143:38: warning: unused variable 'u2' [-Wunused-variable]
  143 |                     int u1 = cur.fi, u2 = j - 1;
      |                                      ^~
portals.cpp:147:25: warning: unused variable 'u1' [-Wunused-variable]
  147 |                     int u1 = j + 1, u2 = cur.se;
      |                         ^~
portals.cpp:147:37: warning: unused variable 'u2' [-Wunused-variable]
  147 |                     int u1 = j + 1, u2 = cur.se;
      |                                     ^~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30