제출 #1273121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273121		sm.22	Tracks in the Snow (BOI13_tracks)	C++20	61.04 / 100	648 ms	208448 KiB

tracks

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
 
#define watch(x)        cerr << "\n" << (#x) << " is " << (x) << "\n";
#define int             long long 
#define ffor(i, a, b)   for(int i=a;i<b;i++)
#define rfor(i, a, b)   for(int i=a-1;i>=b;i--)
#define all(v)          v.begin(), v.end()
#define rall(v)         v.rbegin(), v.rend()
#define pb              push_back
#define fi              first
#define se              second
#define pii             pair<int, int>
#define vi              vector<int> 
#define vvi             vector<vi> 
#define show(a)         for(auto e : a) {cout<<e<<" ";} cout<<"\n"; 
#define pr(a, b, c)     ffor(i, b, c) {cout<<a[i]<<" ";} cout<<"\n";
#define cerr            if(false)cerr
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 10; 
int Mod = 1e9 + 7, INF = 1e18, BASE = 7, Block = 555;

void solve() {

        int n, m; cin>>n>>m; 

        int x[4] = {1, -1, 0, 0}; 
        int y[4] = {0, 0, 1, -1}; 

        char a[n][m]; 
        ffor(i, 0, n) {
                ffor(j, 0, m) cin>>a[i][j];
        }

        deque<array<int, 2>> q; 
        q.push_back({0, 0}); 

        int vis[n][m]; 
        memset(vis, 0x3f, sizeof(vis)); 
        vis[0][0] = 1; 

        while(q.size()) {
                auto v = q.front(); q.pop_front(); 

                ffor(i, 0, 4) {
                        int nx = v[0] + x[i]; 
                        int ny = v[1] + y[i]; 

                        if(!(nx >= 0 && nx < n && ny >= 0 && ny < m) || a[nx][ny] == '.') continue; 

                        int w = a[nx][ny] != a[v[0]][v[1]]; 
                        if(vis[nx][ny] > vis[v[0]][v[1]] + w) {
                                vis[nx][ny] = vis[v[0]][v[1]] + w; 
                                if(w == 0) q.push_front({nx, ny}); 
                                else q.push_back({nx, ny}); 
                        }
                }
        }
        int ans = 0; 
        ffor(i, 0, n) {
                ffor(j, 0, n) if(a[i][j]!='.') {ans = max(ans, vis[i][j]); }
        }
        cout<<ans<<"\n"; 
}

signed main() { 
 
        ios_base::sync_with_stdio(false); 
        cin.tie(NULL); 

        int t = 1; //cin>>t; 
 
        while(t--) solve();
 
        return 0; 
}

• Subtask 1: 21.6667 / 30
• Subtask 2: 39.375 / 70