| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1012940 | 2024-07-02T22:21:17 Z | parentoni | Tracks in the Snow (BOI13_tracks) | C++17 | 336 ms | 152076 KB |
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define print(x) for (auto el: x) cout << el << " "; cout << '\n'
using ll = long long;
using llb = long double;
using vl = vector<ll>;
using pll = pair<ll,ll>;
// functions
void setIO(string s) {freopen((s + ".in").c_str(), "r", stdin);freopen((s + ".out").c_str(), "w", stdout);}
void yes() { cout<<"YES\n"; }
void no() { cout<<"NO\n"; }
// geometry
const double PI = 3.14159265358979323846;
double DEG_to_RAD (double d) {return d*PI/180.0;}
double RAD_to_DEG (double r) {return r*180.0/ PI;}
// values
const ll INF = 1e18;
const ll MOD = 1000000007;
const ll MAX_N = 4000;
ll h, w;
ll dx[4] = {1,-1,0,0};
ll dy[4] = {0,0,1,-1};
vector<vector<bool>> board; // 0 if F, 1 if R;
vector<vector<bool>> visited;
vector<vl> adj;
deque<pair<pll, ll>> q;
ll bfs() {
q.push_back({{1,1}, 1});
visited[1][1] = true;
ll ans = 1;
while(!q.empty()) {
ans = max(ans, q.front().second);
pll cord = q.front().first; ll sc = q.front().second;
//cout << cord.first << " " << cord.second << " " << q.front().second<< endl;
q.pop_front();
for (int i=0;i<4;i++) {
if (visited[cord.first + dx[i]][cord.second + dy[i]]) continue;
if (board[cord.first + dx[i]][cord.second + dy[i]] != board[cord.first][cord.second]) {
q.push_back({{cord.first+dx[i], cord.second+dy[i]}, sc+1});
} else {
q.push_front({{cord.first+dx[i], cord.second+dy[i]}, sc});
}
visited[cord.first + dx[i]][cord.second + dy[i]] = true;
}
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> h >> w; board.resize(h+2); visited.resize(h+2);
for (auto &el: board) el.resize(w+2);
for (auto &el: visited) el.resize(w+2);
fill(visited[0].begin(),visited[0].end(), 1);
for (int i=0;i<=h+1;i++) {visited[i][0] = true; visited[i][w+1] = true;}
fill(visited[h+1].begin(), visited[h+1].end(), 1);
for (int i=1;i<=h;i++) {
string t; cin >> t;
for (int j=1;j<=w;j++) {
board[i][j] = t[j] == 'F'?1:0;
visited[i][j] = t[j] == '.'?1:0;
}
}
cout << bfs() << "\n";
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 8 ms | 600 KB | Output isn't correct |
| 2 | Incorrect | 0 ms | 348 KB | Output isn't correct |
| 3 | Correct | 1 ms | 348 KB | Output is correct |
| 4 | Correct | 4 ms | 1116 KB | Output is correct |
| 5 | Correct | 1 ms | 348 KB | Output is correct |
| 6 | Incorrect | 0 ms | 344 KB | Output isn't correct |
| 7 | Correct | 0 ms | 348 KB | Output is correct |
| 8 | Correct | 1 ms | 344 KB | Output is correct |
| 9 | Correct | 0 ms | 348 KB | Output is correct |
| 10 | Correct | 2 ms | 348 KB | Output is correct |
| 11 | Incorrect | 1 ms | 604 KB | Output isn't correct |
| 12 | Incorrect | 3 ms | 604 KB | Output isn't correct |
| 13 | Correct | 1 ms | 520 KB | Output is correct |
| 14 | Correct | 1 ms | 348 KB | Output is correct |
| 15 | Correct | 6 ms | 664 KB | Output is correct |
| 16 | Incorrect | 7 ms | 604 KB | Output isn't correct |
| 17 | Incorrect | 4 ms | 604 KB | Output isn't correct |
| 18 | Correct | 4 ms | 1116 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 856 KB | Output isn't correct |
| 2 | Incorrect | 21 ms | 860 KB | Output isn't correct |
| 3 | Correct | 129 ms | 4928 KB | Output is correct |
| 4 | Correct | 30 ms | 1624 KB | Output is correct |
| 5 | Incorrect | 23 ms | 2908 KB | Output isn't correct |
| 6 | Correct | 318 ms | 46064 KB | Output is correct |
| 7 | Incorrect | 1 ms | 856 KB | Output isn't correct |
| 8 | Incorrect | 1 ms | 856 KB | Output isn't correct |
| 9 | Correct | 1 ms | 348 KB | Output is correct |
| 10 | Correct | 1 ms | 348 KB | Output is correct |
| 11 | Incorrect | 1 ms | 860 KB | Output isn't correct |
| 12 | Correct | 1 ms | 348 KB | Output is correct |
| 13 | Incorrect | 21 ms | 1072 KB | Output isn't correct |
| 14 | Incorrect | 12 ms | 856 KB | Output isn't correct |
| 15 | Incorrect | 4 ms | 604 KB | Output isn't correct |
| 16 | Correct | 13 ms | 688 KB | Output is correct |
| 17 | Correct | 55 ms | 1628 KB | Output is correct |
| 18 | Incorrect | 17 ms | 1712 KB | Output isn't correct |
| 19 | Correct | 30 ms | 1652 KB | Output is correct |
| 20 | Correct | 31 ms | 1528 KB | Output is correct |
| 21 | Incorrect | 76 ms | 2908 KB | Output isn't correct |
| 22 | Incorrect | 23 ms | 2908 KB | Output isn't correct |
| 23 | Incorrect | 120 ms | 2640 KB | Output isn't correct |
| 24 | Incorrect | 35 ms | 3072 KB | Output isn't correct |
| 25 | Correct | 152 ms | 4696 KB | Output is correct |
| 26 | Correct | 268 ms | 152076 KB | Output is correct |
| 27 | Correct | 278 ms | 83416 KB | Output is correct |
| 28 | Correct | 336 ms | 46016 KB | Output is correct |
| 29 | Incorrect | 281 ms | 45196 KB | Output isn't correct |
| 30 | Correct | 291 ms | 57596 KB | Output is correct |
| 31 | Incorrect | 291 ms | 5000 KB | Output isn't correct |
| 32 | Incorrect | 240 ms | 50132 KB | Output isn't correct |