Submission #336872

#TimeUsernameProblemLanguageResultExecution timeMemory
33687212tqianPortals (BOI14_portals)C++17
70 / 100
1020 ms117484 KiB
#pragma GCC optimize ("O3") #pragma GCC target ("sse4") #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <iostream> #include <iomanip> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <unordered_map> #include <vector> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; typedef double db; typedef string str; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef pair<db, db> pd; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<ll> vl; typedef vector<db> vd; typedef vector<str> vs; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<pd> vpd; #define mp make_pair #define f first #define s second #define sz(x) (int) (x).size() #define all(x) begin(x), end(x) #define rall(x) (x).rbegin(), (x).rend() #define sor(x) sort(all(x)) #define rsz resize #define resz resize #define ins insert #define ft front() #define bk back() #define pf push_front #define pb push_back #define eb emplace_back #define lb lower_bound #define ub upper_bound #define f1r(i, a, b) for (int i = (a); i < (b); ++i) #define f0r(i, a) f1r(i, 0, a) #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define F0R(i, a) FOR(i,0,a) #define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i) #define R0F(i, a) ROF(i, 0, a) #define trav(a, x) for (auto& a : x) mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count()); template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } template<class T> using V = vector<T>; #ifdef LOCAL #define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__); #else #define dbg(...) 17; #endif template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; } template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr> ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; } template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; } template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); } constexpr int pct(int x) { return __builtin_popcount(x); } constexpr int bits(int x) { return 31 - __builtin_clz(x); } // floor(log2(x)) namespace input { template<class T> void re(complex<T>& x); template<class T1, class T2> void re(pair<T1, T2>& p); template<class T> void re(vector<T>& a); template<class T, int SZ> void re(array<T, SZ>& a); template<class T> void re(T& x) { cin >> x; } void re(double& x) { string t; re(t); x = stod(t); } void re(ld& x) { string t; re(t); x = stold(t); } template<class T, class... Ts> void re(T& t, Ts&... ts) { re(t); re(ts...); } template<class T> void re(complex<T>& x) { T a, b; re(a, b); x = cd(a, b); } template<class T1, class T2> void re(pair<T1, T2>& p) { re(p.f, p.s); } template<class T> void re(vector<T>& a) { F0R(i, sz(a)) re(a[i]); } template<class T, int SZ> void re(array<T, SZ>& a) { F0R(i, SZ) re(a[i]); } } using namespace input; namespace output { void pr(int x) { cout << x; } void pr(long x) { cout << x; } void pr(ll x) { cout << x; } void pr(unsigned x) { cout << x; } void pr(unsigned long x) { cout << x; } void pr(unsigned long long x) { cout << x; } void pr(float x) { cout << x; } void pr(double x) { cout << x; } void pr(ld x) { cout << x; } void pr(char x) { cout << x; } void pr(const char* x) { cout << x; } void pr(const string& x) { cout << x; } void pr(bool x) { pr(x ? "true" : "false"); } template<class T> void pr(const complex<T>& x) { cout << x; } template<class T1, class T2> void pr(const pair<T1, T2>& x); template<class T> void pr(const T& x); template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { pr(t); pr(ts...); } template<class T1, class T2> void pr(const pair<T1,T2>& x) { pr("{", x.f, ", ", x.s, "}"); } template<class T> void pr(const T& x) { pr("{"); // const iterator needed for vector<bool> bool fst = 1; for (const auto& a: x) pr(!fst ? ", " : "", a), fst = 0; pr("}"); } void ps() { pr("\n"); } // print w/ spaces template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); } void pc() { pr("]\n"); } // debug w/ commas template<class T, class... Ts> void pc(const T& t, const Ts&... ts) { pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); } } using namespace output; namespace io { void setIn(string s) { freopen(s.c_str(), "r", stdin); } void setOut(string s) { freopen(s.c_str(), "w", stdout); } void setIO(string s = "") { cin.sync_with_stdio(0); cin.tie(0); if (sz(s)) { setIn(s + ".in"), setOut(s + ".out"); } } } using namespace io; const int MOD = 1e9 + 7; // 998244353; const ld PI = acos((ld) -1); typedef std::decay <decltype(MOD)>::type mod_t; struct mi { mod_t val; explicit operator mod_t() const { return val; } mi() { val = 0; } mi(const long long& v) { val = (-MOD <= v && v <= MOD) ? v : v % MOD; if (val < 0) val += MOD; } friend std::istream& operator >> (std::istream& in, mi& a) { long long x; std::cin >> x; a = mi(x); return in; } friend std::ostream& operator << (std::ostream& os, const mi& a) { return os << a.val; } friend void pr(const mi& a) { pr(a.val); } friend void re(mi& a) { long long x; cin >> x; a = mi(x); } friend bool operator == (const mi& a, const mi& b) { return a.val == b.val; } friend bool operator != (const mi& a, const mi& b) { return !(a == b); } friend bool operator < (const mi& a, const mi& b) { return a.val < b.val; } friend bool operator > (const mi& a, const mi& b) { return a.val > b.val; } friend bool operator <= (const mi& a, const mi& b) { return a.val <= b.val; } friend bool operator >= (const mi& a, const mi& b) { return a.val >= b.val; } mi operator - () const { return mi(-val); } mi& operator += (const mi& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; } mi& operator -= (const mi& m) { if ((val -= m.val) < 0) val += MOD; return *this; } mi& operator *= (const mi& m) { val = (long long) val * m.val % MOD; return *this; } friend mi pow(mi a, long long p) { mi ans = 1; assert(p >= 0); for (; p; p /= 2, a *= a) if (p & 1) ans *= a; return ans; } friend mi inv(const mi& a) { assert(a != 0); return pow(a, MOD - 2); } mi& operator /= (const mi& m) { return (*this) *= inv(m); } friend mi operator + (mi a, const mi& b) { return a += b; } friend mi operator - (mi a, const mi& b) { return a -= b; } friend mi operator * (mi a, const mi& b) { return a *= b; } friend mi operator / (mi a, const mi& b) { return a /= b; } }; typedef pair<mi, mi> pmi; typedef vector<mi> vmi; typedef vector<pmi> vpmi; const int N = 1005; const int M = N*N; short dx[4] = {0, 0, 1, -1}; short dy[4] = {1, -1, 0, 0}; short vis[M]; short dist[M]; short g[N][N]; short close[N][N]; template <class C, bool directed> struct Dijkstra { int SZ; std::vector<C> dist; std::vector<std::vector<std::pair<int, C>>> adj; void init(int _SZ) { SZ = _SZ; adj.clear(); adj.resize(SZ); } void ae(int u, int v, C cost) { adj[u].emplace_back(v, cost); if (!directed) adj[v].emplace_back(u, cost); } void gen(int st) { dist = std::vector<C>(SZ, std::numeric_limits<C>::max()); typedef std::pair<C, int> T; std::priority_queue<T, std::vector<T>, std::greater<T>> pq; auto ad = [&](int a, C b) { if (dist[a] <= b) return; pq.push({dist[a] = b, a}); }; ad(st, 0); while (!pq.empty()) { auto x = pq.top(); pq.pop(); if (dist[x.second] < x.first) continue; for (auto& y: adj[x.second]) { ad(y.first, x.first + y.second); } } } }; int main() { setIO(""); int r, c; re(r, c); Dijkstra<short, true> D; D.init(r*c); pi st; pi ed; f0r(i, r) { string line; re(line); f0r(j, c) { if (line[j] == '#') g[i][j] = 1; if (line[j] == 'S') st = {i, j}; if (line[j] == 'C') ed = {i, j}; } } auto wall = [&](int i, int j) -> bool { if (i==0||j==0||i==r-1||j==c-1) return 1; f0r(d, 4) { int ni = i+dx[d]; int nj = j+dy[d]; if (g[ni][nj]) return 1; } return 0; }; auto conv = [&](int a, int b) -> int { return a*c+b; }; auto ae = [&](int w, int x, int y, int z, short we) { int u = conv(w, x); int v = conv(y, z); D.ae(u,v,we); D.ae(v,u,we); }; auto ao = [&](int w, int x, int y, int z, short we) { int u = conv(w, x); int v = conv(y, z); D.ae(u,v,we); }; list<int> que; f0r(i, r) { f0r(j, c) { if (wall(i,j)) { que.pb(conv(i,j)); vis[conv(i,j)]=1; } } } while (!que.empty()) { int s = que.front(); que.pop_front(); f0r(d, 4) { int i = s/c; int j = s%c; int ni = i + dx[d]; int nj = j + dy[d]; if (ni<0||nj<0||ni>=r||nj>=c) continue; if (g[ni][nj]) continue; int nxt = ni*c+nj; if (vis[nxt]) continue; vis[nxt] = 1; close[ni][nj] = close[i][j]+1; que.pb(nxt); } } f0r(i, r) { // furthest to the left int cur = 0; f0r(j, c) { if (g[i][j]) { cur = j+1; } else { ao(i,j,i,cur,close[i][j]+1); } } cur = c-1; for (int j = c-1; j >= 0; j--) { if (g[i][j]) { cur = j-1; } else { ao(i,j,i,cur,close[i][j]+1); } } } f0r(j, c) { int cur = 0; f0r(i, r) { if (g[i][j]) { cur = i+1; } else { ao(i,j,cur,j,close[i][j]+1); } } cur = r-1; for (int i = r-1; i >= 0; i--) { if (g[i][j]) { cur = i-1; } else { ao(i,j,cur,j,close[i][j]+1); } } } f0r(i, r) { f0r(j, c-1) { if (g[i][j]||g[i][j+1]) continue; ae(i,j,i,j+1,1); } } f0r(j, c) { f0r(i, r-1) { if (g[i][j]||g[i+1][j]) continue; ae(i,j,i+1,j,1); } } D.gen(conv(st.f,st.s)); cout << (D.dist[conv(ed.f,ed.s)]) << '\n'; return 0; }

Compilation message (stderr)

portals.cpp: In function 'void io::setIn(std::string)':
portals.cpp:153:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  153 |     void setIn(string s) { freopen(s.c_str(), "r", stdin); }
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
portals.cpp: In function 'void io::setOut(std::string)':
portals.cpp:154:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  154 |     void setOut(string s) { freopen(s.c_str(), "w", stdout); }
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...