oj.uz

Submission #828026

# Submission time Handle Problem Language Result Execution time Memory
828026 2023-08-17T01:58:37 Z bachhoangxuan Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 615 ms 160124 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 || 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();
}

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
30.0 / 30.0

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

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31448 KB Output is correct
2 Correct 43 ms 22624 KB Output is correct
3 Correct 271 ms 125628 KB Output is correct
4 Correct 88 ms 44748 KB Output is correct
5 Correct 209 ms 94364 KB Output is correct
6 Correct 615 ms 139488 KB Output is correct
7 Correct 13 ms 32852 KB Output is correct
8 Correct 12 ms 31416 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 12 ms 32208 KB Output is correct
12 Correct 1 ms 1620 KB Output is correct
13 Correct 47 ms 22620 KB Output is correct
14 Correct 26 ms 14612 KB Output is correct
15 Correct 26 ms 16084 KB Output is correct
16 Correct 19 ms 8584 KB Output is correct
17 Correct 119 ms 48236 KB Output is correct
18 Correct 107 ms 47668 KB Output is correct
19 Correct 88 ms 44772 KB Output is correct
20 Correct 66 ms 41328 KB Output is correct
21 Correct 165 ms 97524 KB Output is correct
22 Correct 193 ms 94360 KB Output is correct
23 Correct 203 ms 78616 KB Output is correct
24 Correct 194 ms 96412 KB Output is correct
25 Correct 523 ms 125712 KB Output is correct
26 Correct 330 ms 160124 KB Output is correct
27 Correct 435 ms 152280 KB Output is correct
28 Correct 578 ms 139352 KB Output is correct
29 Correct 546 ms 137812 KB Output is correct
30 Correct 513 ms 140992 KB Output is correct
31 Correct 439 ms 101220 KB Output is correct
32 Correct 397 ms 141088 KB Output is correct