oj.uz

Submission #1099344

# Submission time Handle Problem Language Result Execution time Memory
1099344 2024-10-11T08:02:45 Z theSkeleton Tracks in the Snow (BOI13_tracks) C++17
89.0625 / 100
 2000 ms 246356 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define space <<' '<<
#define endl '\n'
#define inf 1e14
#define F first
#define S second
#define PB push_back
#define PF push_front
#define md(a) ((a+mod)%mod)
#define MP(a,b) make_pair(a,b)
#define MT(a,b,c) make_tuple(a,b,c)
typedef long long ll;
using namespace std;
template<typename t> using heap=
priority_queue<t,vector<t>,greater<t>>;
const ll mx = 4005;
ll D[mx][mx];
char s[mx][mx];
bool seen[mx][mx];
set<pair<ll,pair<ll,ll>>> l;
pair<ll,ll> n[]={MP(0,1),MP(0,-1),MP(1,0),MP(-1,0)};
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll h,w;cin>>h>>w;
    for(ll i=0;i<h;i++)
        for(ll j=0;j<w;j++){
            cin>>s[i][j];
            D[i][j]=2e7;
        }
    ll o=0;
    D[0][0]=1;
    l.insert(MP(1,MP(0,0)));
    if(s[0][0]=='.'){
        cout<<0;
        return 0;
    }
    while(!l.empty()){
        auto d=l.begin()->S;
        l.erase(l.begin());
        if(seen[d.F][d.S])
            continue;
        seen[d.F][d.S]=1;
        o=max(o,D[d.F][d.S]);
        for(ll p,x,y,i=0;i<4;i++){
            x=d.F+n[i].F,y=d.S+n[i].S;
            if(0<=x&&x<h&&0<=y&&y<w)
            if(s[x][y]!='.'){
                p=s[d.F][d.S]!=s[x][y];
                if(D[d.F][d.S]+p<D[x][y]){
                    D[x][y]=D[d.F][d.S]+p;
                    l.insert(MP(D[x][y],MP(x,y)));
                }
            } 
        }
    }
    cout<<o;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 8796 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 22 ms 8660 KB Output is correct
5 Correct 6 ms 4464 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 6 ms 3932 KB Output is correct
11 Correct 7 ms 3420 KB Output is correct
12 Correct 13 ms 4700 KB Output is correct
13 Correct 6 ms 4444 KB Output is correct
14 Correct 5 ms 4440 KB Output is correct
15 Correct 30 ms 8796 KB Output is correct
16 Correct 38 ms 8796 KB Output is correct
17 Correct 19 ms 8336 KB Output is correct
18 Correct 24 ms 8668 KB Output is correct

Subtask #2
59.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 46116 KB Output is correct
2 Correct 113 ms 29164 KB Output is correct
3 Correct 434 ms 170128 KB Output is correct
4 Correct 137 ms 55376 KB Output is correct
5 Correct 255 ms 113808 KB Output is correct
6 Execution timed out 2064 ms 246356 KB Time limit exceeded
7 Correct 21 ms 48220 KB Output is correct
8 Correct 20 ms 46200 KB Output is correct
9 Correct 4 ms 1116 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 20 ms 47452 KB Output is correct
12 Correct 2 ms 2268 KB Output is correct
13 Correct 113 ms 29168 KB Output is correct
14 Correct 61 ms 19292 KB Output is correct
15 Correct 27 ms 21080 KB Output is correct
16 Correct 55 ms 10960 KB Output is correct
17 Correct 277 ms 59844 KB Output is correct
18 Correct 92 ms 58964 KB Output is correct
19 Correct 138 ms 55380 KB Output is correct
20 Correct 110 ms 51136 KB Output is correct
21 Correct 272 ms 117352 KB Output is correct
22 Correct 243 ms 113748 KB Output is correct
23 Correct 507 ms 97268 KB Output is correct
24 Correct 210 ms 115792 KB Output is correct
25 Correct 326 ms 169552 KB Output is correct
26 Correct 1544 ms 147232 KB Output is correct
27 Execution timed out 2024 ms 182096 KB Time limit exceeded
28 Execution timed out 2105 ms 246356 KB Time limit exceeded
29 Execution timed out 2056 ms 234832 KB Time limit exceeded
30 Execution timed out 2098 ms 223428 KB Time limit exceeded
31 Correct 1705 ms 129876 KB Output is correct
32 Correct 1854 ms 175688 KB Output is correct