oj.uz

Submission #31342

# Submission time Handle Problem Language Result Execution time Memory
31342 2017-08-19T01:53:50 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];
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(u, 0, sizeof u);
        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 (u[X][Y] || g[X][Y]=='.') continue;
        u[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 << endl;
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 49488 KB Output isn't correct
2 Incorrect 6 ms 33488 KB Output isn't correct
3 Incorrect 3 ms 33488 KB Output isn't correct
4 Incorrect 19 ms 45352 KB Output isn't correct
5 Incorrect 9 ms 34692 KB Output isn't correct
6 Incorrect 9 ms 33488 KB Output isn't correct
7 Incorrect 6 ms 33488 KB Output isn't correct
8 Incorrect 6 ms 33736 KB Output isn't correct
9 Incorrect 13 ms 33488 KB Output isn't correct
10 Incorrect 13 ms 34796 KB Output isn't correct
11 Incorrect 3 ms 36488 KB Output isn't correct
12 Incorrect 23 ms 38724 KB Output isn't correct
13 Incorrect 13 ms 34696 KB Output isn't correct
14 Incorrect 13 ms 34692 KB Output isn't correct
15 Incorrect 49 ms 38596 KB Output isn't correct
16 Incorrect 56 ms 49484 KB Output isn't correct
17 Incorrect 43 ms 40076 KB Output isn't correct
18 Incorrect 19 ms 45352 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 35000 KB Output isn't correct
2 Incorrect 209 ms 63488 KB Output isn't correct
3 Incorrect 1409 ms 293248 KB Output isn't correct
4 Incorrect 329 ms 71032 KB Output isn't correct
5 Incorrect 1103 ms 572780 KB Output isn't correct
6 Memory limit exceeded 833 ms 1048576 KB Memory limit exceeded
7 Incorrect 16 ms 34572 KB Output isn't correct
8 Incorrect 16 ms 35004 KB Output isn't correct
9 Incorrect 9 ms 35204 KB Output isn't correct
10 Incorrect 6 ms 34232 KB Output isn't correct
11 Incorrect 16 ms 33956 KB Output isn't correct
12 Incorrect 9 ms 34768 KB Output isn't correct
13 Incorrect 209 ms 63480 KB Output isn't correct
14 Incorrect 119 ms 50976 KB Output isn't correct
15 Incorrect 139 ms 66476 KB Output isn't correct
16 Incorrect 79 ms 47628 KB Output isn't correct
17 Incorrect 563 ms 108004 KB Output isn't correct
18 Incorrect 749 ms 161208 KB Output isn't correct
19 Incorrect 339 ms 71028 KB Output isn't correct
20 Incorrect 316 ms 91816 KB Output isn't correct
21 Incorrect 823 ms 183304 KB Output isn't correct
22 Incorrect 1106 ms 572784 KB Output isn't correct
23 Incorrect 1043 ms 181984 KB Output isn't correct
24 Incorrect 1012 ms 380776 KB Output isn't correct
25 Execution timed out 2000 ms 561500 KB Execution timed out
26 Incorrect 1216 ms 990392 KB Output isn't correct
27 Memory limit exceeded 796 ms 1048576 KB Memory limit exceeded
28 Memory limit exceeded 783 ms 1048576 KB Memory limit exceeded
29 Memory limit exceeded 759 ms 1048576 KB Memory limit exceeded
30 Memory limit exceeded 616 ms 1048576 KB Memory limit exceeded
31 Execution timed out 2000 ms 808404 KB Execution timed out
32 Execution timed out 2000 ms 677184 KB Execution timed out