oj.uz

Submission #1099315

# Submission time Handle Problem Language Result Execution time Memory
1099315 2024-10-11T07:15:51 Z theSkeleton Tracks in the Snow (BOI13_tracks) C++17
34.5833 / 100
 2000 ms 1048576 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 int mx = 4005;
int h,w;
bool seen[mx][mx];
char state[mx][mx];
deque<pair<int,int>> l[2];
pair<int,int> nei[]={MP(0,1),MP(0,-1),MP(1,0),MP(-1,0)};
bool c(int i,int j){
    return (i<0||h<=i||j<0||w<=j);
}
int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>h>>w;
    for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
        cin>>state[i][j];
    int pc=0,cnt=0;
    char cc=state[h-1][w-1];
    l[pc].PB(MP(h-1,w-1));
    if(cc=='.'){
        cout<<0;
        return 0;
    }
    while(!l[pc].empty()){
        pair<int,int> r,d=l[pc].back();
        seen[d.F][d.S]=1;
        l[pc].pop_back();
        for(int i=0;i<4;i++){
            r=MP(d.F+nei[i].F,d.S+nei[i].S);
            if(!c(r.F,r.S))
            if (state[r.F][r.S]!='.'&&!seen[r.F][r.S]){
                if(state[r.F][r.S]==cc)
                    l[pc].push_front(MP(r.F,r.S));
                else
                    l[!pc].push_front(MP(r.F,r.S));
            }
        }
        if(l[pc].empty()){
            pc=!pc;cnt++;
            cc=((cc=='F')?'R':'F');
        }
    }
    cout<<cnt;
    return 0;
}

Subtask #1
8.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1676 ms 1048576 KB Execution killed with signal 9
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1145 ms 79276 KB Output is correct
4 Execution timed out 2068 ms 934564 KB Time limit exceeded
5 Execution timed out 2061 ms 590724 KB Time limit exceeded
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1103 ms 78508 KB Output is correct
8 Execution timed out 2108 ms 940800 KB Time limit exceeded
9 Correct 5 ms 4696 KB Output is correct
10 Runtime error 1931 ms 1048576 KB Execution killed with signal 9
11 Execution timed out 2101 ms 933672 KB Time limit exceeded
12 Runtime error 1770 ms 1048576 KB Execution killed with signal 9
13 Execution timed out 2060 ms 554760 KB Time limit exceeded
14 Execution timed out 2081 ms 558492 KB Time limit exceeded
15 Runtime error 1746 ms 1048576 KB Execution killed with signal 9
16 Runtime error 1635 ms 1048576 KB Execution killed with signal 9
17 Execution timed out 2095 ms 1039244 KB Time limit exceeded
18 Execution timed out 2072 ms 904868 KB Time limit exceeded

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30300 KB Output is correct
2 Execution timed out 2140 ms 960384 KB Time limit exceeded
3 Execution timed out 2079 ms 393952 KB Time limit exceeded
4 Execution timed out 2088 ms 355372 KB Time limit exceeded
5 Correct 136 ms 32848 KB Output is correct
6 Runtime error 1735 ms 1048576 KB Execution killed with signal 9
7 Correct 10 ms 31832 KB Output is correct
8 Correct 10 ms 30296 KB Output is correct
9 Execution timed out 2037 ms 446212 KB Time limit exceeded
10 Correct 1 ms 2396 KB Output is correct
11 Correct 12 ms 31068 KB Output is correct
12 Correct 1 ms 4768 KB Output is correct
13 Execution timed out 2136 ms 1043804 KB Time limit exceeded
14 Execution timed out 2086 ms 576972 KB Time limit exceeded
15 Correct 15 ms 9608 KB Output is correct
16 Execution timed out 2086 ms 616180 KB Time limit exceeded
17 Execution timed out 2047 ms 469576 KB Time limit exceeded
18 Correct 58 ms 19796 KB Output is correct
19 Execution timed out 2092 ms 354564 KB Time limit exceeded
20 Execution timed out 2068 ms 274444 KB Time limit exceeded
21 Execution timed out 2073 ms 262120 KB Time limit exceeded
22 Correct 132 ms 32592 KB Output is correct
23 Execution timed out 2068 ms 546196 KB Time limit exceeded
24 Correct 124 ms 33616 KB Output is correct
25 Correct 210 ms 47332 KB Output is correct
26 Execution timed out 2071 ms 883560 KB Time limit exceeded
27 Execution timed out 2092 ms 790444 KB Time limit exceeded
28 Runtime error 1832 ms 1048576 KB Execution killed with signal 9
29 Execution timed out 2093 ms 857536 KB Time limit exceeded
30 Execution timed out 2087 ms 896368 KB Time limit exceeded
31 Runtime error 1965 ms 1048576 KB Execution killed with signal 9
32 Execution timed out 2055 ms 718624 KB Time limit exceeded