Submission #889490

#	Time	Username	Problem	Language	Result	Execution time	Memory
889490		fragadmsc	Tracks in the Snow (BOI13_tracks)	C++17	3.33 / 100	1129 ms	1048576 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<long long, long long> pii;
typedef long long ll;
typedef long double ld;
 
const long long MAXLOG = 23;
const long long MAXN = 4*1e3+3; // use com cuidado
const long long MOD = 998244353;
const long long inf = 1e9 + 10;
const long long TWO_MOD_INV = 500000004;
 
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define KAMEKAMEHA ios_base::sync_with_stdio(0); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define sz(x) (int)x.size()

vector<ll> dist(MAXN, inf);
vector<pii> grafo[MAXN*MAXN];

void bfs() {
    deque<ll> pq;
    dist[1]=0;
    pq.push_back(1);
    while(!pq.empty()) {
        ll v=pq.front();
        pq.pop_front();
        for(auto i : grafo[v]) {
            if(dist[i.f]>dist[v] + i.s) {
                dist[i.f]=dist[v] + i.s;
                if(i.s) {
                    pq.push_back(i.f);
                } else {
                    pq.push_front(i.f);
                }
            }
        }
    }
}

int main() {
    KAMEKAMEHA
    #ifdef FRAGA     
        freopen("output.out", "w", stdout);
        freopen("err.er", "w", stderr);
    #endif 
    #ifndef FRAGA
        //freopen("cbarn2.in", "r", stdin);
        //freopen("cbarn2.out", "w", stdout);
    #endif
    ll h, w;
    cin>>h>>w;
    char mat[MAXN][MAXN];
    for(ll i=0;i<=h+1;i++) {
        for(ll j=0;j<=w+1;j++) {
            mat[i][j]='.';
        }
    }
    for(ll i=1;i<=h;i++) {
        for(ll j=1;j<=w;j++) {
            cin>>mat[i][j];
        }
    }
    
    for(ll i=1;i<=h;i++) {
        for(ll j=1;j<=w;j++) {
            if(mat[i][j]=='.') continue;
            ll atu=(i-1)*w+j;
            if(mat[i-1][j]!='.') {
                if(mat[i+1][j]==mat[i][j]) {
                    grafo[atu].pb(mp((i-2)*w+j, 0));
                } else {
                    grafo[atu].pb(mp((i-2)*w+j, 1));
                }
            }
            if(mat[i+1][j]!='.') {
                if(mat[i+1][j]==mat[i][j]) {
                    grafo[atu].pb(mp((i)*w+j, 0));
                } else {
                    grafo[atu].pb(mp((i)*w+j, 1));
                }
            }
            if(mat[i][j-1]!='.') {
                if(mat[i][j-1]==mat[i][j]) {
                    grafo[atu].pb(mp((i-1)*w+j-1, 0));
                } else {
                    grafo[atu].pb(mp((i-1)*w+j-1, 1));
                }
            }
            if(mat[i][j+1]!='.') {
                if(mat[i][j+1]==mat[i][j]) {
                    grafo[atu].pb(mp((i-1)*w+j+1, 0));
                } else {
                    grafo[atu].pb(mp((i-1)*w+j+1, 1));
                }
            }
        }
    }
    bfs();
    ll mt=0;
    for(ll i=1;i<=h*w;i++) {
        if(dist[i]!=inf)
            mt=max(mt, dist[i]);
    }
    cout<<mt+1<<endl;
    //indices conflitantes
}

• Subtask 1: 3.3333333333333335 / 30
• Subtask 2: 0 / 70