oj.uz

답안 #559632

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559632 2022-05-10T10:36:16 Z zaneyu Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 652 ms 131040 KB 
/*input
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//order_of_key #of elements less than x
// find_by_order kth element
typedef unsigned long long int ll;

#define ld long double
#define pii pair<int,int>
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=4e3+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"");
    return out;
}
ll mult(ll a,ll b){
    if(a<0) a+=MOD;
    return (a*b)%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
string arr[maxn];
int dist[maxn][maxn];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int32_t main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m;
    cin>>n>>m;
    REP(i,n) cin>>arr[i];
    deque<pii> dq;
    REP(i,n) REP(j,m) dist[i][j]=INF;
    dist[0][0]=1;
    dq.pb({0,0});
    int ans=0;
    while(sz(dq)){
        pii z=dq.front();
        dq.pop_front();
        REP(k,4){
            int x=z.f+dx[k],y=z.s+dy[k];
            if(x<0 or x>=n or y<0 or y>=m) continue;
            if(arr[x][y]=='.') continue;
            int d=dist[z.f][z.s]+(arr[x][y]!=arr[z.f][z.s]);
            if(d<dist[x][y]){
                dist[x][y]=d;
                if(d==dist[z.f][z.s]) dq.push_front({x,y});
                else dq.pb({x,y});
            }
        }
    }
    REP(i,n) REP(j,m) if(arr[i][j]!='.') MXTO(ans,dist[i][j]);
    cout<<ans;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 3924 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 8 ms 3584 KB Output is correct
5 Correct 3 ms 2004 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 584 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 3 ms 1748 KB Output is correct
11 Correct 3 ms 1512 KB Output is correct
12 Correct 6 ms 2176 KB Output is correct
13 Correct 3 ms 2124 KB Output is correct
14 Correct 3 ms 2004 KB Output is correct
15 Correct 11 ms 3972 KB Output is correct
16 Correct 14 ms 3928 KB Output is correct
17 Correct 10 ms 3800 KB Output is correct
18 Correct 7 ms 3540 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 16084 KB Output is correct
2 Correct 41 ms 14760 KB Output is correct
3 Correct 241 ms 96468 KB Output is correct
4 Correct 69 ms 30296 KB Output is correct
5 Correct 176 ms 65960 KB Output is correct
6 Correct 652 ms 110400 KB Output is correct
7 Correct 11 ms 16728 KB Output is correct
8 Correct 8 ms 16084 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 8 ms 16472 KB Output is correct
12 Correct 1 ms 1108 KB Output is correct
13 Correct 43 ms 14676 KB Output is correct
14 Correct 26 ms 9492 KB Output is correct
15 Correct 23 ms 10328 KB Output is correct
16 Correct 21 ms 5800 KB Output is correct
17 Correct 113 ms 32656 KB Output is correct
18 Correct 89 ms 32264 KB Output is correct
19 Correct 75 ms 30272 KB Output is correct
20 Correct 63 ms 27864 KB Output is correct
21 Correct 128 ms 68172 KB Output is correct
22 Correct 192 ms 66000 KB Output is correct
23 Correct 223 ms 55576 KB Output is correct
24 Correct 146 ms 67164 KB Output is correct
25 Correct 467 ms 96356 KB Output is correct
26 Correct 420 ms 130772 KB Output is correct
27 Correct 495 ms 131040 KB Output is correct
28 Correct 646 ms 110496 KB Output is correct
29 Correct 642 ms 107936 KB Output is correct
30 Correct 552 ms 113732 KB Output is correct
31 Correct 533 ms 72168 KB Output is correct
32 Correct 450 ms 120696 KB Output is correct