oj.uz

Submission #1099341

# Submission time Handle Problem Language Result Execution time Memory
1099341 2024-10-11T08:01:25 Z theSkeleton Tracks in the Snow (BOI13_tracks) C++17
89.0625 / 100
 2000 ms 242092 KB 
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#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;
}

Compilation message

tracks.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization("O3")
      | 
tracks.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("unroll-loops")
      |

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 8784 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 24 ms 8540 KB Output is correct
5 Correct 6 ms 4444 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 2 ms 1628 KB Output is correct
10 Correct 5 ms 3932 KB Output is correct
11 Correct 7 ms 3420 KB Output is correct
12 Correct 14 ms 4696 KB Output is correct
13 Correct 5 ms 4648 KB Output is correct
14 Correct 6 ms 4444 KB Output is correct
15 Correct 28 ms 9032 KB Output is correct
16 Correct 42 ms 8800 KB Output is correct
17 Correct 25 ms 8288 KB Output is correct
18 Correct 25 ms 8544 KB Output is correct

Subtask #2
59.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 46064 KB Output is correct
2 Correct 105 ms 28448 KB Output is correct
3 Correct 450 ms 165544 KB Output is correct
4 Correct 141 ms 54100 KB Output is correct
5 Correct 260 ms 110932 KB Output is correct
6 Execution timed out 2105 ms 242092 KB Time limit exceeded
7 Correct 22 ms 48216 KB Output is correct
8 Correct 20 ms 46172 KB Output is correct
9 Correct 4 ms 1112 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 21 ms 47464 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct
13 Correct 103 ms 28536 KB Output is correct
14 Correct 61 ms 19036 KB Output is correct
15 Correct 31 ms 20828 KB Output is correct
16 Correct 53 ms 10840 KB Output is correct
17 Correct 261 ms 58440 KB Output is correct
18 Correct 124 ms 57684 KB Output is correct
19 Correct 142 ms 54120 KB Output is correct
20 Correct 117 ms 50132 KB Output is correct
21 Correct 279 ms 114772 KB Output is correct
22 Correct 257 ms 110928 KB Output is correct
23 Correct 509 ms 94996 KB Output is correct
24 Correct 227 ms 113008 KB Output is correct
25 Correct 560 ms 165316 KB Output is correct
26 Correct 1513 ms 143732 KB Output is correct
27 Execution timed out 2004 ms 178004 KB Time limit exceeded
28 Execution timed out 2080 ms 242000 KB Time limit exceeded
29 Execution timed out 2063 ms 230484 KB Time limit exceeded
30 Execution timed out 2065 ms 219212 KB Time limit exceeded
31 Correct 1714 ms 127060 KB Output is correct
32 Correct 1793 ms 171288 KB Output is correct