oj.uz

Submission #31339

# Submission time Handle Problem Language Result Execution time Memory
31339 2017-08-18T23:21:37 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){
        q[0]=t[0];
        q[1]=t[1];
    }
    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;
        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)+1;
}
int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    fox1(l, n){
        fox1(l2, m){
            cin >> g[l][l2];
        }
    }
    fox1(l, n){
        fox1(l2, m){
            if (!u[l][l2] && g[l][l2]!='.'){
                //cout << "*";
                while(!t[0].empty()) t[0].pop();
                while(!t[1].empty()) t[1].pop();
                dfs(l, l2);
                //cout << l << ' ' << l2 << ' ' << t[0].size() << ' ' << t[1].size() << 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 33 ms 65148 KB Output isn't correct
2 Incorrect 0 ms 49152 KB Output isn't correct
3 Incorrect 0 ms 49152 KB Output isn't correct
4 Incorrect 19 ms 61024 KB Output isn't correct
5 Incorrect 9 ms 50360 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 0 ms 49404 KB Output isn't correct
9 Incorrect 0 ms 49152 KB Output isn't correct
10 Incorrect 6 ms 50460 KB Output isn't correct
11 Incorrect 3 ms 52148 KB Output isn't correct
12 Incorrect 16 ms 54392 KB Output isn't correct
13 Incorrect 9 ms 50356 KB Output isn't correct
14 Incorrect 0 ms 50352 KB Output isn't correct
15 Incorrect 26 ms 54264 KB Output isn't correct
16 Incorrect 36 ms 65148 KB Output isn't correct
17 Incorrect 19 ms 55748 KB Output isn't correct
18 Incorrect 9 ms 61020 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 50664 KB Output isn't correct
2 Incorrect 106 ms 79144 KB Output isn't correct
3 Incorrect 866 ms 308920 KB Output isn't correct
4 Incorrect 239 ms 86692 KB Output isn't correct
5 Incorrect 763 ms 588444 KB Output isn't correct
6 Memory limit exceeded 746 ms 1048576 KB Memory limit exceeded
7 Incorrect 9 ms 50236 KB Output isn't correct
8 Incorrect 6 ms 50660 KB Output isn't correct
9 Incorrect 3 ms 50868 KB Output isn't correct
10 Incorrect 0 ms 49896 KB Output isn't correct
11 Incorrect 16 ms 49616 KB Output isn't correct
12 Incorrect 0 ms 50432 KB Output isn't correct
13 Incorrect 129 ms 79148 KB Output isn't correct
14 Incorrect 66 ms 66644 KB Output isn't correct
15 Incorrect 99 ms 82140 KB Output isn't correct
16 Incorrect 63 ms 63284 KB Output isn't correct
17 Incorrect 363 ms 123664 KB Output isn't correct
18 Incorrect 553 ms 176868 KB Output isn't correct
19 Incorrect 236 ms 86692 KB Output isn't correct
20 Incorrect 209 ms 107484 KB Output isn't correct
21 Incorrect 533 ms 198972 KB Output isn't correct
22 Incorrect 843 ms 588444 KB Output isn't correct
23 Incorrect 583 ms 197652 KB Output isn't correct
24 Incorrect 569 ms 396444 KB Output isn't correct
25 Execution timed out 2000 ms 577164 KB Execution timed out
26 Incorrect 1359 ms 1006060 KB Output isn't correct
27 Memory limit exceeded 759 ms 1048576 KB Memory limit exceeded
28 Memory limit exceeded 763 ms 1048576 KB Memory limit exceeded
29 Memory limit exceeded 759 ms 1048576 KB Memory limit exceeded
30 Memory limit exceeded 729 ms 1048576 KB Memory limit exceeded
31 Execution timed out 2000 ms 824072 KB Execution timed out
32 Execution timed out 2000 ms 695292 KB Execution timed out