# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
59136 |
2018-07-20T16:14:18 Z |
Benq |
Portals (BOI14_portals) |
C++14 |
|
1000 ms |
96844 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 1000;
int R,C, distWall[MX][MX], dist[MX][MX];
vector<pair<pi,int>> adj[MX][MX];
char g[MX][MX];
int xd[4] = {0,1,0,-1}, yd[4] = {1,0,-1,0};
bool isWall(int x, int y) {
if (x < 0 || x >= R || y < 0 || y >= C) return 1;
return g[x][y] == '#';
}
void genWall() {
queue<pi> q;
F0R(i,R) F0R(j,C) distWall[i][j] = MOD;
F0R(i,R) F0R(j,C) {
if (isWall(i,j)) distWall[i][j] = 0;
else {
F0Rd(z,4) if (isWall(i+xd[z],j+yd[z])) {
distWall[i][j] = 1;
q.push({i,j});
}
}
}
while (sz(q)) {
auto a = q.front(); q.pop();
F0R(i,4) {
pi A = {a.f+xd[i],a.s+yd[i]};
if (isWall(A.f,A.s)) continue;
if (distWall[A.f][A.s] != MOD) continue;
distWall[A.f][A.s] = distWall[a.f][a.s]+1;
q.push(A);
}
}
}
void genEdges() {
F0R(i,R) F0R(j,C) if (g[i][j] != '#' && (j == 0 || g[i][j-1] == '#')) {
int J = j; while (!isWall(i,J+1)) J++;
FOR(J2,j,J+1) {
adj[i][J2].pb({{i,j},distWall[i][J2]});
adj[i][J2].pb({{i,J},distWall[i][J2]});
}
j = J+1;
}
F0R(j,C) F0R(i,R) if (g[i][j] != '#' && (i == 0 || g[i-1][j] == '#')) {
int I = i; while (!isWall(I+1,j)) I++;
FOR(I2,i,I+1) {
adj[I2][j].pb({{i,j},distWall[I2][j]});
adj[I2][j].pb({{I,j},distWall[I2][j]});
}
i = I+1;
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> R >> C;
F0R(i,R) F0R(j,C) cin >> g[i][j];
genWall();
genEdges();
pi st,en;
F0R(i,R) F0R(j,C) {
if (g[i][j] == 'S') st = {i,j};
if (g[i][j] == 'C') en = {i,j};
}
F0R(i,R) F0R(j,C) dist[i][j] = MOD;
priority_queue<pair<int,pi>,vector<pair<int,pi>>,greater<pair<int,pi>>> p;
p.push({dist[st.f][st.s] = 0,st});
while (sz(p)) {
auto a = p.top(); p.pop();
if (dist[a.s.f][a.s.s] < a.f) continue;
for (auto x: adj[a.s.f][a.s.s]) if (dist[x.f.f][x.f.s] > x.s+a.f)
p.push({dist[x.f.f][x.f.s] = x.s+a.f,x.f});
F0R(z,4) {
pi A = {a.s.f+xd[z],a.s.s+yd[z]};
if (isWall(A.f,A.s)) continue;
if (dist[A.f][A.s] > a.f+1)
p.push({dist[A.f][A.s] = a.f+1,A});
}
}
cout << dist[en.f][en.s];
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
23800 KB |
Output is correct |
2 |
Correct |
21 ms |
23912 KB |
Output is correct |
3 |
Correct |
21 ms |
23944 KB |
Output is correct |
4 |
Correct |
28 ms |
23944 KB |
Output is correct |
5 |
Correct |
26 ms |
24024 KB |
Output is correct |
6 |
Correct |
29 ms |
24308 KB |
Output is correct |
7 |
Correct |
26 ms |
24308 KB |
Output is correct |
8 |
Correct |
26 ms |
24308 KB |
Output is correct |
9 |
Correct |
26 ms |
24308 KB |
Output is correct |
10 |
Correct |
21 ms |
24308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
24308 KB |
Output is correct |
2 |
Correct |
26 ms |
24308 KB |
Output is correct |
3 |
Correct |
22 ms |
24308 KB |
Output is correct |
4 |
Correct |
26 ms |
24308 KB |
Output is correct |
5 |
Correct |
22 ms |
24308 KB |
Output is correct |
6 |
Correct |
25 ms |
24308 KB |
Output is correct |
7 |
Correct |
27 ms |
24308 KB |
Output is correct |
8 |
Correct |
26 ms |
24308 KB |
Output is correct |
9 |
Correct |
29 ms |
24724 KB |
Output is correct |
10 |
Correct |
30 ms |
24728 KB |
Output is correct |
11 |
Correct |
27 ms |
24728 KB |
Output is correct |
12 |
Correct |
29 ms |
24736 KB |
Output is correct |
13 |
Correct |
28 ms |
24756 KB |
Output is correct |
14 |
Correct |
26 ms |
24756 KB |
Output is correct |
15 |
Correct |
32 ms |
24764 KB |
Output is correct |
16 |
Correct |
27 ms |
24764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
24764 KB |
Output is correct |
2 |
Correct |
20 ms |
24764 KB |
Output is correct |
3 |
Correct |
25 ms |
24764 KB |
Output is correct |
4 |
Correct |
21 ms |
24764 KB |
Output is correct |
5 |
Correct |
49 ms |
27332 KB |
Output is correct |
6 |
Correct |
60 ms |
27472 KB |
Output is correct |
7 |
Correct |
42 ms |
27624 KB |
Output is correct |
8 |
Correct |
45 ms |
27700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
27700 KB |
Output is correct |
2 |
Correct |
25 ms |
27700 KB |
Output is correct |
3 |
Correct |
26 ms |
27700 KB |
Output is correct |
4 |
Correct |
22 ms |
27700 KB |
Output is correct |
5 |
Correct |
24 ms |
27700 KB |
Output is correct |
6 |
Correct |
25 ms |
27700 KB |
Output is correct |
7 |
Correct |
25 ms |
27700 KB |
Output is correct |
8 |
Correct |
26 ms |
27700 KB |
Output is correct |
9 |
Correct |
30 ms |
27700 KB |
Output is correct |
10 |
Correct |
22 ms |
27700 KB |
Output is correct |
11 |
Correct |
22 ms |
27700 KB |
Output is correct |
12 |
Correct |
24 ms |
27700 KB |
Output is correct |
13 |
Correct |
23 ms |
27700 KB |
Output is correct |
14 |
Correct |
47 ms |
27700 KB |
Output is correct |
15 |
Correct |
53 ms |
27700 KB |
Output is correct |
16 |
Correct |
49 ms |
27828 KB |
Output is correct |
17 |
Correct |
51 ms |
27828 KB |
Output is correct |
18 |
Correct |
56 ms |
28396 KB |
Output is correct |
19 |
Correct |
48 ms |
28900 KB |
Output is correct |
20 |
Correct |
43 ms |
28964 KB |
Output is correct |
21 |
Correct |
52 ms |
28964 KB |
Output is correct |
22 |
Correct |
41 ms |
28964 KB |
Output is correct |
23 |
Correct |
59 ms |
28964 KB |
Output is correct |
24 |
Correct |
74 ms |
29000 KB |
Output is correct |
25 |
Correct |
22 ms |
29000 KB |
Output is correct |
26 |
Correct |
28 ms |
29000 KB |
Output is correct |
27 |
Correct |
27 ms |
29000 KB |
Output is correct |
28 |
Correct |
37 ms |
29000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
29000 KB |
Output is correct |
2 |
Correct |
25 ms |
29000 KB |
Output is correct |
3 |
Correct |
27 ms |
29000 KB |
Output is correct |
4 |
Correct |
25 ms |
29000 KB |
Output is correct |
5 |
Correct |
27 ms |
29000 KB |
Output is correct |
6 |
Correct |
27 ms |
29000 KB |
Output is correct |
7 |
Correct |
27 ms |
29000 KB |
Output is correct |
8 |
Correct |
22 ms |
29000 KB |
Output is correct |
9 |
Correct |
31 ms |
29000 KB |
Output is correct |
10 |
Correct |
24 ms |
29000 KB |
Output is correct |
11 |
Correct |
22 ms |
29000 KB |
Output is correct |
12 |
Correct |
28 ms |
29000 KB |
Output is correct |
13 |
Correct |
23 ms |
29000 KB |
Output is correct |
14 |
Correct |
35 ms |
29000 KB |
Output is correct |
15 |
Correct |
38 ms |
29000 KB |
Output is correct |
16 |
Correct |
38 ms |
29000 KB |
Output is correct |
17 |
Correct |
50 ms |
29000 KB |
Output is correct |
18 |
Correct |
54 ms |
29000 KB |
Output is correct |
19 |
Correct |
57 ms |
29288 KB |
Output is correct |
20 |
Correct |
58 ms |
29288 KB |
Output is correct |
21 |
Correct |
47 ms |
29288 KB |
Output is correct |
22 |
Correct |
54 ms |
29288 KB |
Output is correct |
23 |
Correct |
51 ms |
29288 KB |
Output is correct |
24 |
Correct |
845 ms |
76640 KB |
Output is correct |
25 |
Execution timed out |
1078 ms |
96844 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |