# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
675129 |
2022-12-27T02:06:29 Z |
vjudge1 |
Portals (BOI14_portals) |
C++17 |
|
349 ms |
17868 KB |
// Make the best become better
// No room for laziness
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e3 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int r, c;
string a[maxN];
pair<int, int> s, t;
int d[maxN][maxN];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<int> row[maxN], col[maxN];
struct TPQRect
{
int x, y, dlab;
bool operator < (const TPQRect& other) const
{
return other.dlab < dlab;
}
bool Valid() const
{
return d[x][y] == dlab;
}
};
void ReadInput()
{
cin >> r >> c;
for(int i=1; i<=r; i++)
{
row[i].pb(0);
row[i].pb(c + 1);
}
for(int i=1; i<=c; i++)
{
col[i].pb(0);
col[i].pb(r + 1);
}
for(int i=1; i<=r; i++)
{
cin >> a[i];
a[i] = ' ' + a[i];
for(int j=1; j<=c; j++)
{
if(a[i][j] == 'S')
s = {i, j};
if(a[i][j] == 'C')
t = {i, j};
if(a[i][j] == '#')
{
row[i].pb(j);
col[j].pb(i);
}
}
}
for(int i=1; i<=r; i++)
sort(row[i].begin(), row[i].end());
for(int i=1; i<=c; i++)
sort(col[i].begin(), col[i].end());
}
void Dijkstra()
{
priority_queue<TPQRect> pq;
memset(d, 3, sizeof d);
d[s.fi][s.se] = 0;
pq.push({s.fi, s.se, 0});
while(!pq.empty())
{
TPQRect R = pq.top();
pq.pop();
if(!R.Valid())
continue;
int x = R.x, y = R.y;
for(int i=0; i<4; i++)
{
int u = x + dx[i], v = y + dy[i];
if(u < 1 || u > r || v < 1 || v > c || a[u][v] == '#')
continue;
if(d[u][v] > d[x][y] + 1)
{
d[u][v] = d[x][y] + 1;
pq.push({u, v, d[u][v]});
}
}
vector<pair<int, int>> vc;
int id = lower_bound(row[x].begin(), row[x].end(), y) - row[x].begin();
vc.pb({x, row[x][id] - 1});
id--;
vc.pb({x, row[x][id] + 1});
id = lower_bound(col[y].begin(), col[y].end(), x) - col[y].begin();
vc.pb({col[y][id] - 1, y});
id--;
vc.pb({col[y][id] + 1, y});
for(int i=0; i<4; i++)
for(int j=0; j<4; j++)
{
int w = abs(x - vc[j].fi) + abs(y - vc[j].se) + 1;
if(d[vc[i].fi][vc[i].se] > d[x][y] + w)
{
d[vc[i].fi][vc[i].se] = d[x][y] + w;
pq.push({vc[i].fi, vc[i].se, d[vc[i].fi][vc[i].se]});
}
}
}
}
void Solve()
{
Dijkstra();
cout << d[t.fi][t.se];
}
int32_t main()
{
//freopen("x.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ReadInput();
Solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8276 KB |
Output is correct |
2 |
Correct |
4 ms |
8276 KB |
Output is correct |
3 |
Correct |
3 ms |
8276 KB |
Output is correct |
4 |
Correct |
4 ms |
8276 KB |
Output is correct |
5 |
Correct |
4 ms |
8276 KB |
Output is correct |
6 |
Correct |
4 ms |
8276 KB |
Output is correct |
7 |
Correct |
4 ms |
8276 KB |
Output is correct |
8 |
Correct |
3 ms |
8276 KB |
Output is correct |
9 |
Correct |
3 ms |
8276 KB |
Output is correct |
10 |
Correct |
3 ms |
8276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8276 KB |
Output is correct |
2 |
Correct |
4 ms |
8276 KB |
Output is correct |
3 |
Correct |
4 ms |
8276 KB |
Output is correct |
4 |
Correct |
4 ms |
8276 KB |
Output is correct |
5 |
Correct |
4 ms |
8276 KB |
Output is correct |
6 |
Correct |
3 ms |
8276 KB |
Output is correct |
7 |
Correct |
4 ms |
8276 KB |
Output is correct |
8 |
Correct |
4 ms |
8276 KB |
Output is correct |
9 |
Correct |
4 ms |
8276 KB |
Output is correct |
10 |
Correct |
4 ms |
8328 KB |
Output is correct |
11 |
Correct |
4 ms |
8276 KB |
Output is correct |
12 |
Correct |
4 ms |
8276 KB |
Output is correct |
13 |
Correct |
4 ms |
8336 KB |
Output is correct |
14 |
Correct |
4 ms |
8276 KB |
Output is correct |
15 |
Correct |
4 ms |
8276 KB |
Output is correct |
16 |
Correct |
5 ms |
8276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8276 KB |
Output is correct |
2 |
Correct |
3 ms |
8276 KB |
Output is correct |
3 |
Correct |
3 ms |
8276 KB |
Output is correct |
4 |
Correct |
4 ms |
8276 KB |
Output is correct |
5 |
Correct |
12 ms |
8816 KB |
Output is correct |
6 |
Correct |
13 ms |
8760 KB |
Output is correct |
7 |
Correct |
13 ms |
8788 KB |
Output is correct |
8 |
Correct |
10 ms |
8660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8276 KB |
Output is correct |
2 |
Correct |
5 ms |
8276 KB |
Output is correct |
3 |
Correct |
4 ms |
8276 KB |
Output is correct |
4 |
Correct |
4 ms |
8276 KB |
Output is correct |
5 |
Correct |
4 ms |
8276 KB |
Output is correct |
6 |
Correct |
4 ms |
8276 KB |
Output is correct |
7 |
Correct |
4 ms |
8276 KB |
Output is correct |
8 |
Correct |
4 ms |
8276 KB |
Output is correct |
9 |
Correct |
4 ms |
8276 KB |
Output is correct |
10 |
Correct |
4 ms |
8276 KB |
Output is correct |
11 |
Correct |
5 ms |
8276 KB |
Output is correct |
12 |
Correct |
5 ms |
8276 KB |
Output is correct |
13 |
Correct |
5 ms |
8276 KB |
Output is correct |
14 |
Correct |
12 ms |
8812 KB |
Output is correct |
15 |
Correct |
17 ms |
8788 KB |
Output is correct |
16 |
Correct |
16 ms |
8788 KB |
Output is correct |
17 |
Correct |
13 ms |
8784 KB |
Output is correct |
18 |
Correct |
15 ms |
8700 KB |
Output is correct |
19 |
Correct |
14 ms |
8464 KB |
Output is correct |
20 |
Correct |
16 ms |
8464 KB |
Output is correct |
21 |
Correct |
15 ms |
8812 KB |
Output is correct |
22 |
Correct |
12 ms |
8788 KB |
Output is correct |
23 |
Correct |
12 ms |
8836 KB |
Output is correct |
24 |
Correct |
13 ms |
8404 KB |
Output is correct |
25 |
Correct |
4 ms |
8276 KB |
Output is correct |
26 |
Correct |
4 ms |
8276 KB |
Output is correct |
27 |
Correct |
3 ms |
8304 KB |
Output is correct |
28 |
Correct |
10 ms |
8660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8276 KB |
Output is correct |
2 |
Correct |
4 ms |
8276 KB |
Output is correct |
3 |
Correct |
4 ms |
8276 KB |
Output is correct |
4 |
Correct |
4 ms |
8276 KB |
Output is correct |
5 |
Correct |
4 ms |
8276 KB |
Output is correct |
6 |
Correct |
5 ms |
8204 KB |
Output is correct |
7 |
Correct |
4 ms |
8276 KB |
Output is correct |
8 |
Correct |
5 ms |
8276 KB |
Output is correct |
9 |
Correct |
4 ms |
8276 KB |
Output is correct |
10 |
Correct |
4 ms |
8304 KB |
Output is correct |
11 |
Correct |
4 ms |
8276 KB |
Output is correct |
12 |
Correct |
4 ms |
8308 KB |
Output is correct |
13 |
Correct |
4 ms |
8276 KB |
Output is correct |
14 |
Correct |
11 ms |
8788 KB |
Output is correct |
15 |
Correct |
13 ms |
8788 KB |
Output is correct |
16 |
Correct |
20 ms |
8844 KB |
Output is correct |
17 |
Correct |
14 ms |
8788 KB |
Output is correct |
18 |
Correct |
16 ms |
8660 KB |
Output is correct |
19 |
Correct |
17 ms |
8468 KB |
Output is correct |
20 |
Correct |
16 ms |
8464 KB |
Output is correct |
21 |
Correct |
13 ms |
8812 KB |
Output is correct |
22 |
Correct |
12 ms |
8824 KB |
Output is correct |
23 |
Correct |
13 ms |
8740 KB |
Output is correct |
24 |
Correct |
286 ms |
17040 KB |
Output is correct |
25 |
Correct |
254 ms |
9876 KB |
Output is correct |
26 |
Correct |
349 ms |
9908 KB |
Output is correct |
27 |
Correct |
264 ms |
9852 KB |
Output is correct |
28 |
Correct |
198 ms |
17668 KB |
Output is correct |
29 |
Correct |
266 ms |
17652 KB |
Output is correct |
30 |
Correct |
284 ms |
17868 KB |
Output is correct |
31 |
Correct |
13 ms |
8404 KB |
Output is correct |
32 |
Correct |
253 ms |
9600 KB |
Output is correct |
33 |
Correct |
5 ms |
8212 KB |
Output is correct |
34 |
Correct |
5 ms |
8276 KB |
Output is correct |
35 |
Correct |
225 ms |
13568 KB |
Output is correct |
36 |
Correct |
4 ms |
8276 KB |
Output is correct |
37 |
Correct |
10 ms |
8660 KB |
Output is correct |
38 |
Correct |
170 ms |
17432 KB |
Output is correct |
39 |
Correct |
187 ms |
17476 KB |
Output is correct |