oj.uz

답안 #497144

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
497144 2021-12-22T15:00:34 Z viethoangpham Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1635 ms 236236 KB 
#include<bits/stdc++.h>
#define faster  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define el "\n"
#define memset(a, x) memset(a, (x), sizeof(a));
#define sz(x) x.size()
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
using ll = long long;
using ld = long double;
using str = string;
const int INF = int(1e9) + 100;
const ll MAXN = (1 << 20) + 55;
const ll MOD = 1e6 + 3;
#define yes cout << "yes" << el;
#define no cout << "no" << el;
#define umap unordered_map
ll gcd(ll x, ll y){
    return !y?x:gcd(y,x%y);
}
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void setIO(str s) {
	setIn(s+".in"); setOut(s+".out");
}
const ll dx[4] = {1, 0, -1, 0};
const ll dy[4] = {0, 1, 0, -1};
ll n, m, ans = 0;
ll cnt[4005][4005];
char grid[4005][4005];
main(){
//    setIO("CodeforcesEasy");
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> grid[i][j];
        }
    }
    deque <pair<ll, ll>> q;
    q.push_front({0, 0});
    cnt[0][0] = 1;
    while (!q.empty()){
        auto temp = q.front();
        q.pop_front();
        ans = max(ans, cnt[temp.f][temp.s]);
        for (int i = 0; i < 4; i++){
            ll cx = temp.f + dx[i];
            ll cy = temp.s + dy[i];
            if (cx < 0 || cy < 0 || cx >= n || cy >= m || cnt[cx][cy] != 0 || grid[cx][cy] == '.') continue;
            if (grid[cx][cy] == grid[temp.f][temp.s]){
                q.push_front({cx, cy});
                cnt[cx][cy] = cnt[temp.f][temp.s];
            }else{
                q.push_back({cx, cy});
                cnt[cx][cy] = cnt[temp.f][temp.s] + 1;
            }
        }
    }
    cout << ans << el;
}

Compilation message

tracks.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main(){
      | ^~~~
tracks.cpp: In function 'void setIn(str)':
tracks.cpp:23:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 | void setIn(str s) { freopen(s.c_str(),"r",stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
tracks.cpp: In function 'void setOut(str)':
tracks.cpp:24:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 6380 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 668 KB Output is correct
4 Correct 18 ms 6052 KB Output is correct
5 Correct 8 ms 3152 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 816 KB Output is correct
9 Correct 2 ms 1104 KB Output is correct
10 Correct 7 ms 2620 KB Output is correct
11 Correct 5 ms 2256 KB Output is correct
12 Correct 11 ms 3392 KB Output is correct
13 Correct 8 ms 3152 KB Output is correct
14 Correct 8 ms 3112 KB Output is correct
15 Correct 31 ms 6064 KB Output is correct
16 Correct 30 ms 6364 KB Output is correct
17 Correct 23 ms 6032 KB Output is correct
18 Correct 16 ms 5888 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 31024 KB Output is correct
2 Correct 140 ms 18156 KB Output is correct
3 Correct 1196 ms 91252 KB Output is correct
4 Correct 310 ms 46408 KB Output is correct
5 Correct 743 ms 71248 KB Output is correct
6 Correct 1635 ms 185020 KB Output is correct
7 Correct 18 ms 32336 KB Output is correct
8 Correct 22 ms 30984 KB Output is correct
9 Correct 6 ms 720 KB Output is correct
10 Correct 3 ms 464 KB Output is correct
11 Correct 19 ms 31748 KB Output is correct
12 Correct 3 ms 1616 KB Output is correct
13 Correct 138 ms 18148 KB Output is correct
14 Correct 80 ms 12340 KB Output is correct
15 Correct 84 ms 16928 KB Output is correct
16 Correct 57 ms 7100 KB Output is correct
17 Correct 343 ms 36192 KB Output is correct
18 Correct 328 ms 51380 KB Output is correct
19 Correct 301 ms 46352 KB Output is correct
20 Correct 261 ms 30424 KB Output is correct
21 Correct 698 ms 63136 KB Output is correct
22 Correct 707 ms 71192 KB Output is correct
23 Correct 701 ms 57488 KB Output is correct
24 Correct 710 ms 61648 KB Output is correct
25 Correct 1425 ms 156996 KB Output is correct
26 Correct 1218 ms 236236 KB Output is correct
27 Correct 1495 ms 226224 KB Output is correct
28 Correct 1592 ms 185168 KB Output is correct
29 Correct 1600 ms 180160 KB Output is correct
30 Correct 1543 ms 192324 KB Output is correct
31 Correct 1075 ms 116724 KB Output is correct
32 Correct 1513 ms 198988 KB Output is correct