oj.uz

Submission #889490

# Submission time Handle Problem Language Result Execution time Memory
889490 2023-12-19T20:06:31 Z fragadmsc Tracks in the Snow (BOI13_tracks) C++17
3.33333 / 100
 1129 ms 1048576 KB 
#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.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 507 ms 832788 KB Execution killed with signal 6
2 Correct 90 ms 392332 KB Output is correct
3 Incorrect 88 ms 392528 KB Output isn't correct
4 Runtime error 409 ms 819852 KB Execution killed with signal 6
5 Incorrect 91 ms 393552 KB Output isn't correct
6 Correct 90 ms 392276 KB Output is correct
7 Incorrect 87 ms 392272 KB Output isn't correct
8 Runtime error 391 ms 796096 KB Execution killed with signal 6
9 Incorrect 88 ms 392528 KB Output isn't correct
10 Runtime error 382 ms 799024 KB Execution killed with signal 6
11 Runtime error 385 ms 801836 KB Execution killed with signal 6
12 Runtime error 409 ms 808528 KB Execution killed with signal 6
13 Incorrect 97 ms 393724 KB Output isn't correct
14 Incorrect 94 ms 393600 KB Output isn't correct
15 Incorrect 111 ms 406352 KB Output isn't correct
16 Runtime error 425 ms 832596 KB Execution killed with signal 6
17 Incorrect 112 ms 399700 KB Output isn't correct
18 Runtime error 408 ms 819928 KB Execution killed with signal 6

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 393040 KB Output isn't correct
2 Runtime error 562 ms 891248 KB Execution killed with signal 6
3 Incorrect 617 ms 654164 KB Output isn't correct
4 Incorrect 189 ms 427860 KB Output isn't correct
5 Incorrect 524 ms 612692 KB Output isn't correct
6 Runtime error 1129 ms 1048576 KB Execution killed with signal 9
7 Incorrect 89 ms 392972 KB Output isn't correct
8 Incorrect 91 ms 393160 KB Output isn't correct
9 Incorrect 98 ms 394496 KB Output isn't correct
10 Incorrect 91 ms 392928 KB Output isn't correct
11 Incorrect 89 ms 392700 KB Output isn't correct
12 Incorrect 89 ms 392788 KB Output isn't correct
13 Runtime error 519 ms 890964 KB Execution killed with signal 6
14 Incorrect 136 ms 420424 KB Output isn't correct
15 Incorrect 124 ms 406628 KB Output isn't correct
16 Incorrect 132 ms 418900 KB Output isn't correct
17 Incorrect 299 ms 512764 KB Output isn't correct
18 Incorrect 216 ms 448080 KB Output isn't correct
19 Incorrect 190 ms 427804 KB Output isn't correct
20 Incorrect 209 ms 453968 KB Output isn't correct
21 Incorrect 397 ms 548440 KB Output isn't correct
22 Incorrect 523 ms 612436 KB Output isn't correct
23 Incorrect 502 ms 631380 KB Output isn't correct
24 Incorrect 423 ms 542304 KB Output isn't correct
25 Incorrect 618 ms 622420 KB Output isn't correct
26 Runtime error 1046 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1067 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1117 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1103 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1084 ms 1048576 KB Execution killed with signal 9
31 Runtime error 1082 ms 1048576 KB Execution killed with signal 9
32 Runtime error 1088 ms 1048576 KB Execution killed with signal 9