제출 #668321

#제출 시각아이디문제언어결과실행 시간메모리
668321Do_you_copy포탈들 (BOI14_portals)C++17
20 / 100
30 ms43472 KiB
/* I find it wholesome to be alone the greater part of the time. To be in company, even with the best, is soon wearisome and dissipating. I love to be alone. I never found the companion that was so companionable as solitude. */ #include <bits/stdc++.h> #define pb push_back #define fi first #define se second #define faster ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; using ll = long long; using ld = long double; using pii = pair <int, int>; mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1000 + 10; //const int Mod = 1e9 + 7; //const int inf = int n, m; bool visited[maxN][maxN]; int dx[] = {0, 0, -1, 1}; int dy[] = {-1, 1, 0, 0}; int far[maxN][maxN][4]; string s[maxN]; int ans[maxN][maxN]; vector <pii> adj[maxN][maxN]; void bfs(pii u, pii v){ queue <pii> Q; Q.push(u); visited[u.fi][u.se] = 1; while (!Q.empty()){ auto r = Q.front(); Q.pop(); for (auto i: adj[r.fi][r.se]){ if (visited[i.fi][i.se]) continue; visited[i.fi][i.se] = 1; Q.push({i.fi, i.se}); ans[i.fi][i.se] = ans[r.fi][r.se] + 1; } } } void Solve(int d){ if (d & 1){ for (int i = 1; i <= n; ++i){ for (int j = 1; j <= m; ++j){ if (s[i][j] == '#'){ far[i][j][d] = -1; continue; } far[i][j][d] = far[i - dx[d]][j - dy[d]][d] + 1; } } } else{ for (int i = n; i >= 1; --i){ for (int j = m; j >= 1; --j){ if (s[i][j] == '#'){ far[i][j][d] = -1; continue; } far[i][j][d] = far[i - dx[d]][j - dy[d]][d] + 1; } } } } void Init(){ cin >> n >> m; for (int i = 0; i < m + 2; ++i) s[0].pb('#'); for (int i = 0; i < m + 2; ++i) s[n + 1].pb('#'); pii u, v; for (int i = 1; i <= n; ++i){ cin >> s[i]; s[i] = "#" + s[i] + "#"; for (int j = 1; j <= m; ++j){ if (s[i][j] == 'S') u = {i, j}; else if (s[i][j] == 'C') v = {i, j}; } } memset(far, -1, sizeof(far)); for (int i = 0; i < 4; ++i) Solve(i); for (int i = 1; i <= n; ++i){ for (int j = 1; j <= m; ++j){ pii minn = {0x3f3f3f3f, 0}; for (int d = 0; d < 4; ++d){ minn = min(minn, {far[i][j][d], d}); if (s[i + dx[d]][j + dy[d]] != '#'){ adj[i][j].pb({i + dx[d], j + dy[d]}); } } for (int d = 0; d < 4; ++d){ if (far[i][j][d] == minn.fi) continue; adj[i - far[i][j][minn.se] * dx[minn.se]][j - far[i][j][minn.se] * dy[minn.se]].pb( {i - far[i][j][d] * dx[d], j - far[i][j][d] * dy[d]}); } } } bfs(u, v); cout << ans[v.fi][v.se]; } #define debug #define taskname "test" signed main(){ faster if (fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } int tt = 1; //cin >> tt; while (tt--){ Init(); } if (fopen("timeout.txt", "r")){ ofstream timeout("timeout.txt"); timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000); timeout.close(); #ifndef debug cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n"; #endif // debug } }

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

portals.cpp: In function 'int main()':
portals.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
portals.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(taskname".out", "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...