답안 #858788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
858788	2023-10-09T07:47:55 Z	wibulord	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	638 ms	132992 KB

tracks

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define db long double
#define fi first
#define se second
#define pb emplace_back

#define vi vector<int>
#define vii vector<pair<int,int>>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pdd pair<db, db>
#define iii pair<int, pair<int, int> >

#define ms(s, n) memset(s, n, sizeof(s))
#define all(a) a.begin(), a.end()
#define uni(a) (sort(all(a)), a.resize(unique(all(a))-a.begin()))
#define sz(a) int((a).size())

#define bit(x) bitset<10>((x))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (1 &((x) >> (i)))
#define clz(x) __builtin_clz((x))
#define ctz(x) __builtin_ctz((x))
#define popc(x) __builtin_popcount((x))
#define clzll(x) __builtin_clzll((x))
#define ctzll(x) __builtin_ctzll((x))
#define popcll(x) __builtin_popcountll((x))

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i)
#define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--)
#define rep(i, a) for (auto i : a)

using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

void print(int x) {cerr << x;}
void print(long long x) {cerr << x;}
void print(long double x) {cerr << x;}
void print(double x) {cerr << x;}
void print(unsigned long long x) {cerr << x;}
void print(char x) {cerr << x;}
void print(bool x) {cerr << (x ? "True" : "False");}
void print(string x) {cerr << x;}

template <typename T,typename H>
void print(pair<T,H> a) {cerr << "("; print(a.fi); cerr << ','; print(a.se); cerr << ')';}
template <typename T>
void print(T vec) {int cnt=0; cerr << "{"; rep(x,vec) cerr << (cnt++?",":""), print(x); cerr << '}';}

void show() {}
template <typename Head, typename ...Tail>
void show(Head H, Tail ...T){
    print(H);
    if (sizeof...(T)) cerr << ", ";
    show(T...);
}
#define debug(X...) cerr << "LINE "  << __LINE__ << " - " <<  "[" << #X << "] = [", show(X), cerr << "]\n"

template<typename T1,typename T2> bool ckmax(T1 &x,const T2 &y){if(x<y){x=y; return 1;} return 0;}
template<typename T1,typename T2> bool ckmin(T1 &x,const T2 &y){if(y<x){x=y; return 1;} return 0;}

inline int gcd(int x,int y){while(y){int tmp=y;y=x%y;x=tmp;} return (x);}
inline int lcm(int x,int y){return (int)(x*y)/gcd(x,y);}

void read(){}
template <typename Head, typename ...Tail>
void read(Head &H, Tail &...T)
{
    int sign = 0;
    char c;
    for (c = getchar(); !isdigit(c); c = getchar())
        if (c == '-') sign = 1;
    H = c - '0';
    for (c = getchar(); isdigit(c); c = getchar())
        H = H * 10 + c - '0';
    if (sign) H = -H;
    read(T...);
}

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return l + rd()% (r-l+1);}

const int MOD = 1000000007;
const int mod = 998244353;
const int oo = 1061109567;
const long long INF = 4557430888798830399;
const double PI = acos(-1);
const int N = 4e3 + 1, M = 1e2 + 5;

/*
     /\_/\
    (= ._.)
    / >?  \>$
*/
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};

int n, m;
int d[N][N];
char a[N][N];

bool check(int x, int y){
    if(x < 1 || y < 1) return 0;
    if(x > n || y > m) return 0;
    if(d[x][y] || a[x][y] == '.') return 0;
    return 1;
}

void sol(){
    cin >> n >> m;
    FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j];
    int ans = 0; 
    deque<pii> dq; dq.push_back({1, 1});
    d[1][1] = 1;
    while(sz(dq)){
        int x = dq[0].fi;
        int y = dq[0].se;
        dq.pop_front();
        ckmax(ans, d[x][y]);
        F0R(i, 4){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(check(nx, ny)){
                if(a[x][y] == a[nx][ny]){
                    d[nx][ny] = d[x][y];
                    dq.push_front({nx ,ny});
                }
                else{
                    d[nx][ny] = d[x][y] + 1;
                    dq.push_back({nx ,ny});
                }
            }
        }
    }
    cout << ans << endl;
    // FOR(i, 1, n) FOR(j, 1, m) cout << d[i][j] << " \n"[j == m];
}

signed main(){
    #define TASK "nhap"
    if(fopen(TASK".inp", "r")){
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    fast; int t = 1;
//    cin >> t;
    while(t--) sol();
    clog << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	7516 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	4696 KB	Output is correct
4	Correct	7 ms	7360 KB	Output is correct
5	Correct	3 ms	5724 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	4700 KB	Output is correct
8	Correct	1 ms	4568 KB	Output is correct
9	Correct	1 ms	4696 KB	Output is correct
10	Correct	3 ms	5468 KB	Output is correct
11	Correct	2 ms	5468 KB	Output is correct
12	Correct	6 ms	6236 KB	Output is correct
13	Correct	3 ms	5852 KB	Output is correct
14	Correct	3 ms	5980 KB	Output is correct
15	Correct	11 ms	7444 KB	Output is correct
16	Correct	15 ms	7772 KB	Output is correct
17	Correct	9 ms	7260 KB	Output is correct
18	Correct	7 ms	7256 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	32224 KB	Output is correct
2	Correct	43 ms	18048 KB	Output is correct
3	Correct	264 ms	73692 KB	Output is correct
4	Correct	76 ms	35176 KB	Output is correct
5	Correct	193 ms	55376 KB	Output is correct
6	Correct	638 ms	107732 KB	Output is correct
7	Correct	11 ms	32856 KB	Output is correct
8	Correct	9 ms	32348 KB	Output is correct
9	Correct	2 ms	2520 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	9 ms	32688 KB	Output is correct
12	Correct	1 ms	4956 KB	Output is correct
13	Correct	42 ms	18164 KB	Output is correct
14	Correct	25 ms	12756 KB	Output is correct
15	Correct	21 ms	15184 KB	Output is correct
16	Correct	21 ms	7916 KB	Output is correct
17	Correct	108 ms	30996 KB	Output is correct
18	Correct	85 ms	37616 KB	Output is correct
19	Correct	71 ms	35216 KB	Output is correct
20	Correct	63 ms	28724 KB	Output is correct
21	Correct	164 ms	54344 KB	Output is correct
22	Correct	202 ms	55528 KB	Output is correct
23	Correct	216 ms	45648 KB	Output is correct
24	Correct	160 ms	51556 KB	Output is correct
25	Correct	365 ms	94644 KB	Output is correct
26	Correct	374 ms	132992 KB	Output is correct
27	Correct	499 ms	115972 KB	Output is correct
28	Correct	624 ms	107988 KB	Output is correct
29	Correct	611 ms	106072 KB	Output is correct
30	Correct	562 ms	109520 KB	Output is correct
31	Correct	502 ms	77032 KB	Output is correct
32	Correct	436 ms	105740 KB	Output is correct