oj.uz

Submission #595044

# Submission time Handle Problem Language Result Execution time Memory
595044 2022-07-13T09:43:25 Z ShivanshJ Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1766 ms 922000 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX=4e3+5;
const int INF=1e18;
const int MOD=1e9+7;
const int MAXL=32;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int g[MAX][MAX][6],h,w; // {T,R,B,L} , vertex-info (4)
bool chk(int x,int y) {
    return (x>=0 && y>=0 && x<h && y<w && g[x][y][4]!=-1);
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //cout<<setprecision(6)<<fixed;
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    cin>>h>>w;
    for(int i=0;i<h;i++) {
        for(int j=0;j<w;j++) {
            char s;
            cin>>s;
            if(s=='R') {
                g[i][j][4]=0;
            } else if(s=='F') {
                g[i][j][4]=1;
            } else {
                g[i][j][4]=-1;
            }
        }
    }
    for(int i=0;i<h;i++) {
        for(int j=0;j<w;j++) {
            for(int z=0;z<4;z++) {
                int nx=i+dx[z],ny=j+dy[z];
                if(chk(nx,ny) && g[nx][ny][4]!=g[i][j][4]) {
                    g[i][j][z]=1;
                }
            }
            g[i][j][5]=-1;
        }
    }
    deque<tuple<int,int,int>>dq; //{x,y,dist}
    dq.push_front({0,0,0});
    int ans=0;
    while(!dq.empty()) {
        tuple<int,int,int>curr=dq.front();
        dq.pop_front();
        int x=get<0>(curr),y=get<1>(curr),d=get<2>(curr);
        if(g[x][y][5]!=-1) {
            continue;
        }
        g[x][y][5]=d;
        ans=max(ans,d);
        for(int i=0;i<4;i++) {
            int nx=x+dx[i],ny=y+dy[i];
            if(!chk(nx,ny) || g[nx][ny][5]!=-1) {
                continue;
            }
            if(g[x][y][i]) {
                dq.push_back({nx,ny,d+1});
            } else {
                dq.push_front({nx,ny,d});
            }
        }
    }
    cout<<(++ans);
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 14208 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 16 ms 10888 KB Output is correct
5 Correct 6 ms 5460 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 5 ms 4436 KB Output is correct
11 Correct 4 ms 3412 KB Output is correct
12 Correct 11 ms 5856 KB Output is correct
13 Correct 6 ms 5556 KB Output is correct
14 Correct 7 ms 5460 KB Output is correct
15 Correct 29 ms 14576 KB Output is correct
16 Correct 31 ms 14232 KB Output is correct
17 Correct 24 ms 13820 KB Output is correct
18 Correct 18 ms 10812 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19156 KB Output is correct
2 Correct 121 ms 80452 KB Output is correct
3 Correct 858 ms 764064 KB Output is correct
4 Correct 215 ms 187852 KB Output is correct
5 Correct 437 ms 443924 KB Output is correct
6 Correct 1766 ms 838528 KB Output is correct
7 Correct 11 ms 19668 KB Output is correct
8 Correct 12 ms 19200 KB Output is correct
9 Correct 5 ms 3284 KB Output is correct
10 Correct 2 ms 1748 KB Output is correct
11 Correct 11 ms 19528 KB Output is correct
12 Correct 2 ms 2008 KB Output is correct
13 Correct 130 ms 80552 KB Output is correct
14 Correct 67 ms 47408 KB Output is correct
15 Correct 71 ms 52328 KB Output is correct
16 Correct 54 ms 32764 KB Output is correct
17 Correct 305 ms 203168 KB Output is correct
18 Correct 273 ms 200356 KB Output is correct
19 Correct 228 ms 187916 KB Output is correct
20 Correct 195 ms 172492 KB Output is correct
21 Correct 507 ms 459436 KB Output is correct
22 Correct 458 ms 443980 KB Output is correct
23 Correct 588 ms 381920 KB Output is correct
24 Correct 473 ms 448864 KB Output is correct
25 Correct 1162 ms 763992 KB Output is correct
26 Correct 1002 ms 897976 KB Output is correct
27 Correct 1270 ms 922000 KB Output is correct
28 Correct 1673 ms 838452 KB Output is correct
29 Correct 1692 ms 823804 KB Output is correct
30 Correct 1477 ms 865252 KB Output is correct
31 Correct 1457 ms 507172 KB Output is correct
32 Correct 1238 ms 901260 KB Output is correct