제출 #1099304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1099304		theSkeleton	Tracks in the Snow (BOI13_tracks)	C++17	34.58 / 100	2130 ms	1048576 KiB

tracks

#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;
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));
    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.333333333333334 / 30
• Subtask 2: 26.25 / 70