| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 675330 |
2022-12-27T04:14:34 Z |
vjudge1 |
Portals (BOI14_portals) |
C++17 |
|
5 ms |
8300 KB |
#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;
}
Compilation message
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;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
8148 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8148 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8148 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8300 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8148 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
8148 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
