제출 #675330

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
675330		vjudge1	포탈들 (BOI14_portals)	C++17	0 / 100	5 ms	8300 KiB

portals

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#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];
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)]});
    }

    if(r[xstart].size() > 1) {
        auto it = r[xstart].upper_bound({ystart, n + m});
        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)]});
    }

    if(c[ystart].size() > 1) {
        auto it2 = c[ystart].upper_bound({xstart, n + m});
        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)]});
            }
        }

        if(r[u.x].size() > 1) {
            auto tmp = r[u.x].upper_bound({u.y, n + m});
            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)]});
            }
        }

        if(c[u.y].size() > 1) {
            auto tmp2 = c[u.y].upper_bound({u.x, n + m});
            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)]});
            }
        }
    }

    if(dp[target] < INF) cout << dp[target];
    else cout << -1;
}
int main()
{
    FastIO
    cin >> n >> m;

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

    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 == '#') {
                if(r[i].size() > 1) {
                    auto it = r[i].upper_bound({j, n + m});
                    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});
                    }
                }

                if(c[j].size() > 1) {
                    auto it2 = c[j].upper_bound({i, n + m});
                    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 : r[i]) cout << u.fi << " " << u.se << " | ";
        cout << '\n';
    }
    **/

    xuli();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

portals.cpp: In function 'void xuli()':
portals.cpp:54:39: warning: narrowing conversion of 'dp[(((u - 1) * m) + v)]' from 'long long int' to 'int' [-Wnarrowing]
   54 |             pq.push({u, v, dp[ID(u, v)]});
      |                            ~~~~~~~~~~~^
portals.cpp:62:59: 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:59: 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:72:61: warning: narrowing conversion of 'dp[(((cur2.std::pair<int, int>::first - 1) * m) + ystart)]' from 'long long int' to 'int' [-Wnarrowing]
   72 |             pq.push({cur2.fi, ystart, dp[ID(cur2.fi, ystart)]});
      |                                       ~~~~~~~~~~~~~~~~~~~~~~^
portals.cpp:74:61: warning: narrowing conversion of 'dp[(((cur2.std::pair<int, int>::second - 1) * m) + ystart)]' from 'long long int' to 'int' [-Wnarrowing]
   74 |             pq.push({cur2.se, ystart, dp[ID(cur2.se, ystart)]});
      |                                       ~~~~~~~~~~~~~~~~~~~~~~^
portals.cpp:91:43: warning: narrowing conversion of 'dp[(((x - 1) * m) + y)]' from 'long long int' to 'int' [-Wnarrowing]
   91 |                 pq.push({x, y, dp[ID(x, y)]});
      |                                ~~~~~~~~~~~^
portals.cpp:100:57: warning: narrowing conversion of 'dp[(((u.Data::x - 1) * m) + tam.std::pair<int, int>::first)]' from 'long long int' to 'int' [-Wnarrowing]
  100 |                 pq.push({u.x, tam.fi, dp[ID(u.x, tam.fi)]});
      |                                       ~~~~~~~~~~~~~~~~~~^
portals.cpp:103:57: warning: narrowing conversion of 'dp[(((u.Data::x - 1) * m) + tam.std::pair<int, int>::second)]' from 'long long int' to 'int' [-Wnarrowing]
  103 |                 pq.push({u.x, tam.se, dp[ID(u.x, tam.se)]});
      |                                       ~~~~~~~~~~~~~~~~~~^
portals.cpp:112:59: warning: narrowing conversion of 'dp[(((tam2.std::pair<int, int>::first - 1) * m) + u.Data::y)]' from 'long long int' to 'int' [-Wnarrowing]
  112 |                 pq.push({tam2.fi, u.y, dp[ID(tam2.fi, u.y)]});
      |                                        ~~~~~~~~~~~~~~~~~~~^
portals.cpp:115:59: warning: narrowing conversion of 'dp[(((tam2.std::pair<int, int>::second - 1) * m) + u.Data::y)]' from 'long long int' to 'int' [-Wnarrowing]
  115 |                 pq.push({tam2.se, u.y, dp[ID(tam2.se, u.y)]});
      |                                        ~~~~~~~~~~~~~~~~~~~^
portals.cpp: In function 'int main()':
portals.cpp:151:29: warning: unused variable 'u1' [-Wunused-variable]
  151 |                         int u1 = cur.fi, u2 = j - 1;
      |                             ^~
portals.cpp:151:42: warning: unused variable 'u2' [-Wunused-variable]
  151 |                         int u1 = cur.fi, u2 = j - 1;
      |                                          ^~
portals.cpp:155:29: warning: unused variable 'u1' [-Wunused-variable]
  155 |                         int u1 = j + 1, u2 = cur.se;
      |                             ^~
portals.cpp:155:41: warning: unused variable 'u2' [-Wunused-variable]
  155 |                         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