oj.uz

Submission #828021

# Submission time Handle Problem Language Result Execution time Memory
828021 2023-08-17T01:52:57 Z bachhoangxuan Tracks in the Snow (BOI13_tracks) C++17
19.7917 / 100
 631 ms 183292 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;
    char f;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;cin >> c;
            if(i==1 && j==1) f=c;
            dist[i][j]=inf;
            d[i][j]=(c=='.'?-1:(c==f?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) 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();
}

Compilation message

tracks.cpp: In function 'void solve()':
tracks.cpp:67:37: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |             d[i][j]=(c=='.'?-1:(c==f?0:1));
      |                                ~~~~~^~~~~

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 6228 KB Output isn't correct
2 Incorrect 0 ms 468 KB Output isn't correct
3 Incorrect 1 ms 724 KB Output isn't correct
4 Correct 7 ms 5656 KB Output is correct
5 Incorrect 4 ms 3540 KB Output isn't correct
6 Incorrect 0 ms 468 KB Output isn't correct
7 Incorrect 1 ms 724 KB Output isn't correct
8 Correct 1 ms 852 KB Output is correct
9 Incorrect 1 ms 1236 KB Output isn't correct
10 Incorrect 3 ms 3028 KB Output isn't correct
11 Correct 2 ms 2260 KB Output is correct
12 Incorrect 5 ms 3284 KB Output isn't correct
13 Incorrect 4 ms 3540 KB Output isn't correct
14 Incorrect 4 ms 3540 KB Output isn't correct
15 Incorrect 11 ms 6740 KB Output isn't correct
16 Incorrect 11 ms 6228 KB Output isn't correct
17 Incorrect 11 ms 6612 KB Output isn't correct
18 Correct 7 ms 5712 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 31632 KB Output isn't correct
2 Incorrect 53 ms 27544 KB Output isn't correct
3 Incorrect 458 ms 183292 KB Output isn't correct
4 Incorrect 135 ms 55548 KB Output isn't correct
5 Incorrect 271 ms 131240 KB Output isn't correct
6 Correct 551 ms 139352 KB Output is correct
7 Incorrect 13 ms 33056 KB Output isn't correct
8 Incorrect 12 ms 31572 KB Output isn't correct
9 Incorrect 3 ms 852 KB Output isn't correct
10 Incorrect 1 ms 724 KB Output isn't correct
11 Incorrect 13 ms 32432 KB Output isn't correct
12 Incorrect 2 ms 1748 KB Output isn't correct
13 Incorrect 53 ms 27596 KB Output isn't correct
14 Incorrect 31 ms 17460 KB Output isn't correct
15 Incorrect 45 ms 19648 KB Output isn't correct
16 Incorrect 23 ms 10328 KB Output isn't correct
17 Incorrect 137 ms 61344 KB Output isn't correct
18 Incorrect 182 ms 61632 KB Output isn't correct
19 Incorrect 134 ms 55524 KB Output isn't correct
20 Incorrect 112 ms 53408 KB Output isn't correct
21 Incorrect 289 ms 131136 KB Output isn't correct
22 Incorrect 256 ms 131176 KB Output isn't correct
23 Incorrect 253 ms 103224 KB Output isn't correct
24 Incorrect 276 ms 135444 KB Output isn't correct
25 Incorrect 631 ms 182348 KB Output isn't correct
26 Correct 321 ms 160192 KB Output is correct
27 Correct 499 ms 152324 KB Output is correct
28 Correct 551 ms 139384 KB Output is correct
29 Correct 548 ms 137704 KB Output is correct
30 Correct 514 ms 141048 KB Output is correct
31 Incorrect 490 ms 101184 KB Output isn't correct
32 Incorrect 447 ms 147032 KB Output isn't correct