oj.uz

Submission #828024

# Submission time Handle Problem Language Result Execution time Memory
828024 2023-08-17T01:57:46 Z bachhoangxuan Tracks in the Snow (BOI13_tracks) C++17
47.7083 / 100
 577 ms 160180 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
//#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e9;
const int mod=998244353;
const int maxn=4005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=20;
const int maxa=1000000;
const int root=3;
/*
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
*/
const int base=101;
int dx[]={1,-1,0,0},
    dy[]={0,0,1,-1};

int n,m;
int d[maxn][maxn],dist[maxn][maxn];

void solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;cin >> c;
            dist[i][j]=inf;
            d[i][j]=(c=='.'?-1:(c=='R'?0:1));
        }
    }
    deque<pii> dq;
    dq.push_back({1,1});dist[1][1]=1;
    int ans=0;
    while(!dq.empty()){
        int x=dq.front().fi,y=dq.front().se;dq.pop_front();
        int dd=dist[x][y];
        ans=max(ans,dd);
        for(int t=0;t<4;t++){
            int xt=x+dx[t],yt=y+dy[t];
            if(xt<=0 || yt<=0 || xt>n || yt>m || d[xt][yt]==-1) continue;
            int nxt=(d[xt][yt]==(dd&1));
            if(dist[xt][yt]>dd+nxt){
                dist[xt][yt]=dd+nxt;
                if(nxt) dq.push_back({xt,yt});
                else dq.push_front({xt,yt});
            }
        }
    }
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
8.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 6100 KB Output isn't correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 1 ms 724 KB Output isn't correct
4 Incorrect 6 ms 5716 KB Output isn't correct
5 Incorrect 3 ms 3284 KB Output isn't correct
6 Correct 0 ms 468 KB Output is correct
7 Incorrect 1 ms 724 KB Output isn't correct
8 Incorrect 1 ms 852 KB Output isn't correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 3 ms 2772 KB Output is correct
11 Incorrect 2 ms 2260 KB Output isn't correct
12 Correct 6 ms 3284 KB Output is correct
13 Incorrect 4 ms 3284 KB Output isn't correct
14 Incorrect 4 ms 3284 KB Output isn't correct
15 Incorrect 10 ms 6228 KB Output isn't correct
16 Incorrect 14 ms 6220 KB Output isn't correct
17 Incorrect 9 ms 5952 KB Output isn't correct
18 Incorrect 8 ms 5700 KB Output isn't correct

Subtask #2
39.375 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 31444 KB Output isn't correct
2 Correct 53 ms 22612 KB Output is correct
3 Incorrect 285 ms 125764 KB Output isn't correct
4 Incorrect 87 ms 44676 KB Output isn't correct
5 Incorrect 200 ms 94348 KB Output isn't correct
6 Correct 577 ms 139416 KB Output is correct
7 Correct 13 ms 32852 KB Output is correct
8 Incorrect 12 ms 31444 KB Output isn't correct
9 Incorrect 2 ms 724 KB Output isn't correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 13 ms 32212 KB Output is correct
12 Incorrect 1 ms 1620 KB Output isn't correct
13 Correct 43 ms 22612 KB Output is correct
14 Incorrect 28 ms 14696 KB Output isn't correct
15 Correct 27 ms 16112 KB Output is correct
16 Correct 19 ms 8532 KB Output is correct
17 Correct 109 ms 48168 KB Output is correct
18 Correct 102 ms 47672 KB Output is correct
19 Incorrect 87 ms 44660 KB Output isn't correct
20 Correct 67 ms 41248 KB Output is correct
21 Correct 170 ms 97444 KB Output is correct
22 Incorrect 192 ms 94296 KB Output isn't correct
23 Incorrect 206 ms 78680 KB Output isn't correct
24 Correct 169 ms 96448 KB Output is correct
25 Incorrect 513 ms 125716 KB Output isn't correct
26 Correct 331 ms 160180 KB Output is correct
27 Incorrect 462 ms 152320 KB Output isn't correct
28 Correct 566 ms 139524 KB Output is correct
29 Correct 559 ms 137700 KB Output is correct
30 Incorrect 498 ms 141076 KB Output isn't correct
31 Correct 420 ms 101108 KB Output is correct
32 Correct 401 ms 141060 KB Output is correct