제출 #552585

#제출 시각아이디문제언어결과실행 시간메모리
552585SmolBrain포탈들 (BOI14_portals)C++17
70 / 100
1095 ms51068 KiB
// Om Namah Shivaya // GM in 101 days #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.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 int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define endl '\n' #define pb push_back #define conts continue #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "YES" << endl #define no cout << "NO" << endl #define ff first #define ss second #define ceil2(x,y) ((x+y-1) / (y)) #define sz(a) a.size() #define setbits(x) __builtin_popcountll(x) #ifndef ONLINE_JUDGE #define debug(x) cout << #x <<" = "; print(x); cout << endl #else #define debug(x) #endif #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) bool iseven(ll n) {if ((n & 1) == 0) return true; return false;} void print(ll t) {cout << t;} void print(int t) {cout << t;} void print(string t) {cout << t;} void print(char t) {cout << t;} void print(double t) {cout << t;} void print(ld t) {cout << t;} template <class T, class V> void print(pair <T, V> p); template <class T> void print(vector <T> v); template <class T> void print(set <T> v); template <class T, class V> void print(map <T, V> v); template <class T> void print(multiset <T> v); template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.ff); cout << ","; print(p.ss); cout << "}";} template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";} template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";} template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";} template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]";} template<typename T> void amin(T &a, T b) { a = min(a, b); } template<typename T> void amax(T &a, T b) { a = max(a, b); } void usaco(string filename) { freopen((filename + ".in").c_str(), "r", stdin); freopen((filename + ".out").c_str(), "w", stdout); } const int MOD = 1e9 + 7; const int maxn = 1e5 + 5; const int inf1 = 1e9 + 5; const ll inf2 = ll(1e18) + 5; int nxtleft[1005][1005], nxtright[1005][1005], nxtup[1005][1005], nxtdown[1005][1005]; bool vis[1005][1005]; int dis[1005][1005], dis2[1005][1005]; int dx[4] = { -1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; void solve(int test_case) { // referred to: https://github.com/tmwilliamlin168/CompetitiveProgramming/blob/master/BtOI/14-Portals.cpp and the official editorial code // initially got WA cuz i misunderstood the problem statement (more like overlooked a particular case) int n, m; cin >> n >> m; vector<vector<char>> a(n + 5, vector<char>(m + 5, '#')); rep1(i, n) rep1(j, m) cin >> a[i][j]; rep1(i, n) { stack<ll> st; rep(j, m + 2) { if (a[i][j] == '#') { while (!st.empty()) { nxtright[i][st.top()] = j; st.pop(); } } else { st.push(j); } } while (!st.empty()) st.pop(); rev(j, m + 1, 0) { if (a[i][j] == '#') { while (!st.empty()) { nxtleft[i][st.top()] = j; st.pop(); } } else { st.push(j); } } } rep1(j, m) { stack<ll> st; rep(i, n + 2) { if (a[i][j] == '#') { while (!st.empty()) { nxtdown[st.top()][j] = i; st.pop(); } } else { st.push(i); } } while (!st.empty()) st.pop(); rev(i, n + 1, 0) { if (a[i][j] == '#') { while (!st.empty()) { nxtup[st.top()][j] = i; st.pop(); } } else { st.push(i); } } } pii start, end; rep1(i, n) rep1(j, m) { if (a[i][j] == 'S') start = {i, j}; else if (a[i][j] == 'C') end = {i, j}; } queue<pii> q; rep(i, n + 2) rep(j, m + 2) { if (a[i][j] != '#') conts; q.push({i, j}); vis[i][j] = 1; dis[i][j] = 0; } while (!q.empty()) { auto [i, j] = q.front(); q.pop(); rep(x, 4) { int i2 = i + dx[x], j2 = j + dy[x]; if (i2 < 0 or i2 > n + 1 or j2 < 0 or j2 > m + 1) conts; if (vis[i2][j2]) conts; q.push({i2, j2}); vis[i2][j2] = 1; dis[i2][j2] = dis[i][j] + 1; } } priority_queue< array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>> > pq; memset(vis, 0, sizeof vis); rep(i, n + 5) rep(j, m + 5) dis2[i][j] = inf1; pq.push({0, start.ff, start.ss}); dis2[start.ff][start.ss] = 0; while (!pq.empty()) { auto [cost, i, j] = pq.top(); pq.pop(); if (vis[i][j]) conts; vis[i][j] = 1; if (i == end.ff and j == end.ss) { cout << cost << endl; return; } rep(x, 4) { int i2 = i + dx[x], j2 = j + dy[x]; if (i2 < 0 or i2 > n + 1 or j2 < 0 or j2 > m + 1) conts; if (vis[i2][j2]) conts; if (a[i2][j2] == '#') conts; // if (cost + 1 < dis2[i2][j2]) { // dis2[i2][j2] = cost + 1; pq.push({cost + 1, i2, j2}); // } } int min_dis_to_wall = dis[i][j]; vector<pii> cells; cells.pb({i, nxtleft[i][j] + 1}); cells.pb({i, nxtright[i][j] - 1}); cells.pb({nxtup[i][j] + 1, j}); cells.pb({nxtdown[i][j] - 1, j}); for (auto [i2, j2] : cells) { int cost2 = cost + min_dis_to_wall; // if (cost2 < dis2[i2][j2]) { // dis2[i2][j2] = cost; pq.push({cost2, i2, j2}); // } } } } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } return 0; }

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

portals.cpp: In function 'void usaco(std::string)':
portals.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
portals.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((filename + ".out").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...