oj.uz

Submission #31340

# Submission time Handle Problem Language Result Execution time Memory
31340 2017-08-18T23:42:17 Z imaxblue Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)

int n, m, X, Y, ans;
char g[4005][4005];
bool u[4005][4005], u2[4005][4005];
queue<pii> t[2], q[2];
void dfs(int X, int Y){
    if (X<1 || Y<1 || X>n || Y>m) return;
    //cout << X << ' ' << Y << endl;
    if (u[X][Y] || g[X][Y]=='.') return;
    u[X][Y]=1;
    if (g[X-1][Y]=='.' || g[X+1][Y]=='.' || g[X][Y-1]=='.' || g[X][Y+1]=='.')
        t[g[X][Y]=='F'].push(mp(X, Y));
    dfs(X-1, Y);
    dfs(X+1, Y);
    dfs(X, Y-1);
    dfs(X, Y+1);
}
int bfs(bool T, bool F){
    if (F){
        memset(u2, 0, sizeof u2);
        q[0]=t[0];
        q[1]=t[1];
    }
    bool k=0;
    if (q[0].empty() && q[1].empty()) return 0;
    while(!q[T].empty()){
        X=q[T].front().x; Y=q[T].front().y; q[T].pop();
        if (X<1 || Y<1 || X>n || Y>m) continue;
        if (u2[X][Y] || g[X][Y]=='.') continue;
        u2[X][Y]=1;
        k=1;
        q[g[X+1][Y]=='F'].push(mp(X+1, Y));
        q[g[X-1][Y]=='F'].push(mp(X-1, Y));
        q[g[X][Y+1]=='F'].push(mp(X, Y+1));
        q[g[X][Y-1]=='F'].push(mp(X, Y-1));
    }
    return bfs(!T, 0)+k;
}
int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    fox1(l, n){
        fox1(l2, m){
            cin >> g[l][l2];
        }
    }
    dfs(1, 1);
    //cout << t[0].size() << ' ' << t[1].size() << endl;
    //cout << bfs(1, 1) << ' ' << bfs(0, 1) << endl;
    ans+=min(bfs(0, 1), bfs(1, 1));
    cout << ans;
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 65152 KB Output isn't correct
2 Incorrect 3 ms 49152 KB Output isn't correct
3 Incorrect 0 ms 49152 KB Output isn't correct
4 Incorrect 3 ms 61016 KB Output isn't correct
5 Incorrect 9 ms 50356 KB Output isn't correct
6 Incorrect 0 ms 49152 KB Output isn't correct
7 Incorrect 0 ms 49152 KB Output isn't correct
8 Incorrect 3 ms 49400 KB Output isn't correct
9 Incorrect 0 ms 49152 KB Output isn't correct
10 Incorrect 3 ms 50456 KB Output isn't correct
11 Incorrect 6 ms 52156 KB Output isn't correct
12 Incorrect 16 ms 54388 KB Output isn't correct
13 Incorrect 3 ms 50356 KB Output isn't correct
14 Incorrect 3 ms 50360 KB Output isn't correct
15 Incorrect 36 ms 54268 KB Output isn't correct
16 Incorrect 49 ms 65152 KB Output isn't correct
17 Incorrect 39 ms 55740 KB Output isn't correct
18 Incorrect 9 ms 61016 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 50664 KB Output isn't correct
2 Incorrect 196 ms 79152 KB Output isn't correct
3 Incorrect 1423 ms 308916 KB Output isn't correct
4 Incorrect 343 ms 86696 KB Output isn't correct
5 Incorrect 1163 ms 588444 KB Output isn't correct
6 Memory limit exceeded 803 ms 1048576 KB Memory limit exceeded
7 Incorrect 9 ms 50240 KB Output isn't correct
8 Incorrect 6 ms 50668 KB Output isn't correct
9 Incorrect 6 ms 50868 KB Output isn't correct
10 Incorrect 6 ms 49900 KB Output isn't correct
11 Incorrect 13 ms 49616 KB Output isn't correct
12 Incorrect 3 ms 50436 KB Output isn't correct
13 Incorrect 213 ms 79144 KB Output isn't correct
14 Incorrect 116 ms 66640 KB Output isn't correct
15 Incorrect 136 ms 82144 KB Output isn't correct
16 Incorrect 113 ms 63292 KB Output isn't correct
17 Incorrect 589 ms 123664 KB Output isn't correct
18 Incorrect 753 ms 176868 KB Output isn't correct
19 Incorrect 246 ms 86696 KB Output isn't correct
20 Incorrect 253 ms 107484 KB Output isn't correct
21 Incorrect 729 ms 198964 KB Output isn't correct
22 Incorrect 1169 ms 588448 KB Output isn't correct
23 Incorrect 1103 ms 197652 KB Output isn't correct
24 Incorrect 893 ms 396444 KB Output isn't correct
25 Execution timed out 2000 ms 577160 KB Execution timed out
26 Incorrect 1346 ms 1006060 KB Output isn't correct
27 Memory limit exceeded 836 ms 1048576 KB Memory limit exceeded
28 Memory limit exceeded 779 ms 1048576 KB Memory limit exceeded
29 Memory limit exceeded 693 ms 1048576 KB Memory limit exceeded
30 Memory limit exceeded 673 ms 1048576 KB Memory limit exceeded
31 Execution timed out 2000 ms 825292 KB Execution timed out
32 Execution timed out 2000 ms 695288 KB Execution timed out