oj.uz

Submission #931371

# Submission time Handle Problem Language Result Execution time Memory
931371 2024-02-21T16:41:37 Z sofija6 Tracks in the Snow (BOI13_tracks) C++14
91.25 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
#define ll int
#define MAXN 4001
using namespace std;
char c[MAXN][MAXN];
ll a[MAXN][MAXN],cur=1,dist[MAXN*MAXN];
bool V[MAXN][MAXN];
set<pair<ll,ll> > s;
vector<ll> G[MAXN*MAXN];
void DFS(ll i,ll j)
{
    a[i][j]=cur;
    V[i][j]=true;
    for (ll x=-1;x<2;x++)
    {
        for (ll y=-1;y<2;y++)
        {
            if (abs(x)+abs(y)==1)
            {
                if (c[i+x][j+y]==c[i][j] && !V[i+x][j+y])
                    DFS(i+x,j+y);
                else if (c[i+x][j+y]!=c[i][j] && V[i+x][j+y] && !s.count({a[i+x][j+y],cur}))
                {
                    G[a[i+x][j+y]].push_back(cur);
                    G[cur].push_back(a[i+x][j+y]);
                    s.insert({a[i+x][j+y],cur});
                }
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll h,w;
    cin >> h >> w;
    for (ll i=1;i<=h;i++)
    {
        for (ll j=1;j<=w;j++)
            cin >> c[i][j];
    }
    for (ll i=1;i<=h;i++)
    {
        for (ll j=1;j<=w;j++)
        {
            if (!V[i][j] && c[i][j]!='.')
            {
                DFS(i,j);
                cur++;
            }
        }
    }
    queue<ll> q;
    q.push(1);
    dist[1]=1;
    ll ans=0;
    while (!q.empty())
    {
        ll i=q.front();
        q.pop();
        ans=max(ans,dist[i]);
        for (ll next : G[i])
        {
            if (!dist[next])
            {
                dist[next]=dist[i]+1;
                q.push(next);
            }
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 387368 KB Output is correct
2 Correct 110 ms 378444 KB Output is correct
3 Correct 110 ms 378656 KB Output is correct
4 Correct 121 ms 386124 KB Output is correct
5 Correct 113 ms 381524 KB Output is correct
6 Correct 108 ms 378368 KB Output is correct
7 Correct 109 ms 378704 KB Output is correct
8 Correct 110 ms 378712 KB Output is correct
9 Correct 112 ms 378960 KB Output is correct
10 Correct 115 ms 381012 KB Output is correct
11 Correct 114 ms 380984 KB Output is correct
12 Correct 127 ms 382292 KB Output is correct
13 Correct 115 ms 381520 KB Output is correct
14 Correct 127 ms 381396 KB Output is correct
15 Correct 142 ms 386948 KB Output is correct
16 Correct 150 ms 387388 KB Output is correct
17 Correct 134 ms 386476 KB Output is correct
18 Correct 120 ms 386384 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 422480 KB Output is correct
2 Correct 238 ms 414288 KB Output is correct
3 Correct 856 ms 588240 KB Output is correct
4 Correct 288 ms 438220 KB Output is correct
5 Correct 1440 ms 809196 KB Output is correct
6 Correct 1324 ms 674288 KB Output is correct
7 Correct 125 ms 424588 KB Output is correct
8 Correct 125 ms 422480 KB Output is correct
9 Correct 116 ms 379476 KB Output is correct
10 Correct 111 ms 378964 KB Output is correct
11 Correct 126 ms 423508 KB Output is correct
12 Correct 112 ms 380240 KB Output is correct
13 Correct 240 ms 414688 KB Output is correct
14 Correct 180 ms 400828 KB Output is correct
15 Correct 181 ms 404812 KB Output is correct
16 Correct 173 ms 392388 KB Output is correct
17 Correct 430 ms 459344 KB Output is correct
18 Correct 407 ms 464776 KB Output is correct
19 Correct 285 ms 438064 KB Output is correct
20 Correct 287 ms 437404 KB Output is correct
21 Correct 563 ms 514644 KB Output is correct
22 Correct 1446 ms 810552 KB Output is correct
23 Correct 739 ms 519524 KB Output is correct
24 Correct 623 ms 559672 KB Output is correct
25 Correct 1641 ms 670800 KB Output is correct
26 Runtime error 548 ms 1048576 KB Execution killed with signal 9
27 Runtime error 600 ms 1048576 KB Execution killed with signal 9
28 Correct 1334 ms 676148 KB Output is correct
29 Correct 1191 ms 728516 KB Output is correct
30 Correct 1167 ms 859004 KB Output is correct
31 Execution timed out 2025 ms 626788 KB Time limit exceeded
32 Runtime error 589 ms 1048576 KB Execution killed with signal 9