oj.uz

Submission #1099295

# Submission time Handle Problem Language Result Execution time Memory
1099295 2024-10-11T06:39:29 Z theSkeleton Tracks in the Snow (BOI13_tracks) C++17
34.5833 / 100
 2000 ms 1048576 KB 
#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 1978 ms 1048576 KB Execution killed with signal 9
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1882 ms 77384 KB Output is correct
4 Execution timed out 2102 ms 962644 KB Time limit exceeded
5 Execution timed out 2077 ms 462696 KB Time limit exceeded
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1850 ms 79404 KB Output is correct
8 Execution timed out 2095 ms 967720 KB Time limit exceeded
9 Correct 8 ms 2908 KB Output is correct
10 Execution timed out 2078 ms 1048576 KB Time limit exceeded
11 Execution timed out 2101 ms 1002600 KB Time limit exceeded
12 Runtime error 1989 ms 1048576 KB Execution killed with signal 9
13 Execution timed out 2101 ms 514060 KB Time limit exceeded
14 Execution timed out 2069 ms 501800 KB Time limit exceeded
15 Execution timed out 2102 ms 813128 KB Time limit exceeded
16 Runtime error 1996 ms 1048576 KB Execution killed with signal 9
17 Execution timed out 2075 ms 966120 KB Time limit exceeded
18 Execution timed out 2091 ms 1001592 KB Time limit exceeded

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31068 KB Output is correct
2 Execution timed out 2128 ms 974008 KB Time limit exceeded
3 Execution timed out 2095 ms 319208 KB Time limit exceeded
4 Execution timed out 2053 ms 355664 KB Time limit exceeded
5 Correct 219 ms 33868 KB Output is correct
6 Execution timed out 2074 ms 789904 KB Time limit exceeded
7 Correct 13 ms 31832 KB Output is correct
8 Correct 13 ms 31064 KB Output is correct
9 Execution timed out 2045 ms 224060 KB Time limit exceeded
10 Correct 1 ms 2392 KB Output is correct
11 Correct 12 ms 31412 KB Output is correct
12 Correct 1 ms 2904 KB Output is correct
13 Execution timed out 2140 ms 998212 KB Time limit exceeded
14 Execution timed out 2073 ms 510760 KB Time limit exceeded
15 Correct 22 ms 10332 KB Output is correct
16 Execution timed out 2057 ms 565112 KB Time limit exceeded
17 Execution timed out 2047 ms 404152 KB Time limit exceeded
18 Correct 79 ms 21192 KB Output is correct
19 Execution timed out 2037 ms 355536 KB Time limit exceeded
20 Execution timed out 2081 ms 213176 KB Time limit exceeded
21 Execution timed out 2017 ms 242340 KB Time limit exceeded
22 Correct 212 ms 33724 KB Output is correct
23 Execution timed out 2089 ms 451664 KB Time limit exceeded
24 Correct 158 ms 34896 KB Output is correct
25 Correct 350 ms 47400 KB Output is correct
26 Execution timed out 2073 ms 908416 KB Time limit exceeded
27 Execution timed out 2041 ms 904404 KB Time limit exceeded
28 Execution timed out 2044 ms 909972 KB Time limit exceeded
29 Execution timed out 2039 ms 774372 KB Time limit exceeded
30 Execution timed out 2088 ms 835160 KB Time limit exceeded
31 Execution timed out 2100 ms 1033376 KB Time limit exceeded
32 Execution timed out 2097 ms 746488 KB Time limit exceeded