oj.uz

Submission #1099297

# Submission time Handle Problem Language Result Execution time Memory
1099297 2024-10-11T06:41:27 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 = 4e3+5;
deque<pair<int,int>> b;
deque<pair<int,int>> g;
char state[mx][mx];
bool seen[mx][mx];
int h,w;
bool c(int i,int j,char s){
    if(i<0||h<=i) return 1;
    if(j<0||w<=j) return 1;
    if(seen[i][j])return 1;
    if(state[i][j]==s){
        g.push_front(MP(i,j));
        return 1;
    }
    if (state[i][j]=='.')
        return 1;
    return 0;
}
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 cnt=0;
    g.PB(MP(h-1,w-1));
    char cc=state[h-1][w-1];
    while((!g.empty())||(!b.empty())){
        cnt++;
        while(!b.empty()){
            auto p=b.back();
            b.pop_back();
            c(p.F+1,p.S,cc);
            c(p.F-1,p.S,cc);
            c(p.F,p.S+1,cc);
            c(p.F,p.S-1,cc);
        }
        while(!g.empty()){
            auto p=g.back();
            g.pop_back();
            bool k=1;
            seen[p.F][p.S]=1;
            k&=c(p.F+1,p.S,cc);
            k&=c(p.F-1,p.S,cc);
            k&=c(p.F,p.S+1,cc);
            k&=c(p.F,p.S-1,cc);
            if(!k)
                b.push_front(p);
        }
        cc=((cc=='F')?'R':'F');
    }
    cout<<cnt;
    return 0;
}

Subtask #1
8.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1678 ms 1048576 KB Execution killed with signal 9
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1217 ms 77328 KB Output is correct
4 Execution timed out 2100 ms 952728 KB Time limit exceeded
5 Execution timed out 2087 ms 623720 KB Time limit exceeded
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1216 ms 77232 KB Output is correct
8 Execution timed out 2081 ms 1019388 KB Time limit exceeded
9 Correct 5 ms 2904 KB Output is correct
10 Runtime error 1867 ms 1048576 KB Execution killed with signal 9
11 Execution timed out 2102 ms 963292 KB Time limit exceeded
12 Runtime error 1949 ms 1048576 KB Execution killed with signal 9
13 Execution timed out 2036 ms 610160 KB Time limit exceeded
14 Execution timed out 2087 ms 613224 KB Time limit exceeded
15 Execution timed out 2075 ms 877308 KB Time limit exceeded
16 Runtime error 1673 ms 1048576 KB Execution killed with signal 9
17 Execution timed out 2057 ms 1002300 KB Time limit exceeded
18 Execution timed out 2097 ms 974040 KB Time limit exceeded

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31064 KB Output is correct
2 Execution timed out 2099 ms 1044400 KB Time limit exceeded
3 Execution timed out 2058 ms 393496 KB Time limit exceeded
4 Execution timed out 2060 ms 355684 KB Time limit exceeded
5 Correct 164 ms 33616 KB Output is correct
6 Runtime error 1940 ms 1048576 KB Execution killed with signal 9
7 Correct 12 ms 31836 KB Output is correct
8 Correct 13 ms 31084 KB Output is correct
9 Execution timed out 2107 ms 344380 KB Time limit exceeded
10 Correct 1 ms 2392 KB Output is correct
11 Correct 13 ms 31580 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Execution timed out 2134 ms 1034164 KB Time limit exceeded
14 Execution timed out 2043 ms 583132 KB Time limit exceeded
15 Correct 18 ms 10328 KB Output is correct
16 Execution timed out 2097 ms 765416 KB Time limit exceeded
17 Execution timed out 2085 ms 591808 KB Time limit exceeded
18 Correct 58 ms 21192 KB Output is correct
19 Execution timed out 2029 ms 355668 KB Time limit exceeded
20 Execution timed out 2024 ms 266488 KB Time limit exceeded
21 Execution timed out 2086 ms 263124 KB Time limit exceeded
22 Correct 166 ms 33616 KB Output is correct
23 Execution timed out 2092 ms 699708 KB Time limit exceeded
24 Correct 144 ms 34496 KB Output is correct
25 Correct 243 ms 46940 KB Output is correct
26 Execution timed out 2076 ms 926752 KB Time limit exceeded
27 Execution timed out 2083 ms 904740 KB Time limit exceeded
28 Runtime error 1869 ms 1048576 KB Execution killed with signal 9
29 Execution timed out 2076 ms 912008 KB Time limit exceeded
30 Execution timed out 2056 ms 935764 KB Time limit exceeded
31 Runtime error 1942 ms 1048576 KB Execution killed with signal 9
32 Execution timed out 2092 ms 804180 KB Time limit exceeded