oj.uz

Submission #1099317

# Submission time Handle Problem Language Result Execution time Memory
1099317 2024-10-11T07:18:52 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;
using std::deque;
using std::make_pair;
using std::cin;
using std::cout;
using std::pair;
int h,w;
bool seen[mx][mx];
char state[mx][mx];
deque<pair<int,int>> l[2];
void c(int i,int j,char s,bool p){
    if(i<0||h<=i||j<0||w<=j)return;
    if (state[i][j]=='.')   return;
    if(seen[i][j])          return;
    if(state[i][j]==s)
        l[p].push_front(MP(i,j));
    else
        l[!p].push_front(MP(i,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()){
        auto d=l[pc].back();
        seen[d.F][d.S]=1;
        l[pc].pop_back();
        c(d.F+1,d.S,cc,pc);
        c(d.F-1,d.S,cc,pc);
        c(d.F,d.S+1,cc,pc);
        c(d.F,d.S-1,cc,pc);
        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 Execution timed out 2070 ms 1048576 KB Time limit exceeded
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1618 ms 76744 KB Output is correct
4 Execution timed out 2112 ms 751272 KB Time limit exceeded
5 Execution timed out 2069 ms 426280 KB Time limit exceeded
6 Correct 0 ms 2392 KB Output is correct
7 Correct 1588 ms 77032 KB Output is correct
8 Execution timed out 2080 ms 779116 KB Time limit exceeded
9 Correct 6 ms 4700 KB Output is correct
10 Execution timed out 2133 ms 865132 KB Time limit exceeded
11 Execution timed out 2131 ms 706616 KB Time limit exceeded
12 Execution timed out 2110 ms 995068 KB Time limit exceeded
13 Execution timed out 2112 ms 334156 KB Time limit exceeded
14 Execution timed out 2051 ms 399044 KB Time limit exceeded
15 Execution timed out 2127 ms 990860 KB Time limit exceeded
16 Execution timed out 2103 ms 1048576 KB Time limit exceeded
17 Execution timed out 2104 ms 826752 KB Time limit exceeded
18 Execution timed out 2059 ms 734528 KB Time limit exceeded

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 30300 KB Output is correct
2 Execution timed out 2099 ms 830004 KB Time limit exceeded
3 Execution timed out 2071 ms 356576 KB Time limit exceeded
4 Execution timed out 2051 ms 268548 KB Time limit exceeded
5 Correct 185 ms 32572 KB Output is correct
6 Execution timed out 2120 ms 1048576 KB Time limit exceeded
7 Correct 15 ms 32088 KB Output is correct
8 Correct 11 ms 30296 KB Output is correct
9 Execution timed out 2041 ms 226052 KB Time limit exceeded
10 Correct 1 ms 2396 KB Output is correct
11 Correct 17 ms 31064 KB Output is correct
12 Correct 1 ms 4696 KB Output is correct
13 Execution timed out 2138 ms 792120 KB Time limit exceeded
14 Execution timed out 2061 ms 405192 KB Time limit exceeded
15 Correct 17 ms 9560 KB Output is correct
16 Execution timed out 2098 ms 549232 KB Time limit exceeded
17 Execution timed out 2051 ms 402612 KB Time limit exceeded
18 Correct 78 ms 20040 KB Output is correct
19 Execution timed out 2061 ms 267440 KB Time limit exceeded
20 Execution timed out 2069 ms 214320 KB Time limit exceeded
21 Execution timed out 2041 ms 259380 KB Time limit exceeded
22 Correct 151 ms 32596 KB Output is correct
23 Execution timed out 2058 ms 309196 KB Time limit exceeded
24 Correct 142 ms 33616 KB Output is correct
25 Correct 342 ms 47432 KB Output is correct
26 Execution timed out 2097 ms 807568 KB Time limit exceeded
27 Execution timed out 2088 ms 704616 KB Time limit exceeded
28 Execution timed out 2112 ms 1020868 KB Time limit exceeded
29 Execution timed out 2110 ms 703760 KB Time limit exceeded
30 Execution timed out 2087 ms 788052 KB Time limit exceeded
31 Execution timed out 2100 ms 1024068 KB Time limit exceeded
32 Execution timed out 2033 ms 587124 KB Time limit exceeded