oj.uz

Submission #931369

# Submission time Handle Problem Language Result Execution time Memory
931369 2024-02-21T16:37:53 Z sofija6 Tracks in the Snow (BOI13_tracks) C++14
91.25 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
#define ll long long
#define MAXN 4010
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 239 ms 391416 KB Output is correct
2 Correct 158 ms 386356 KB Output is correct
3 Correct 160 ms 378624 KB Output is correct
4 Correct 164 ms 389204 KB Output is correct
5 Correct 148 ms 382976 KB Output is correct
6 Correct 150 ms 378280 KB Output is correct
7 Correct 150 ms 378688 KB Output is correct
8 Correct 158 ms 378812 KB Output is correct
9 Correct 143 ms 379216 KB Output is correct
10 Correct 152 ms 382288 KB Output is correct
11 Correct 145 ms 382036 KB Output is correct
12 Correct 158 ms 384400 KB Output is correct
13 Correct 152 ms 383604 KB Output is correct
14 Correct 148 ms 383056 KB Output is correct
15 Correct 179 ms 390740 KB Output is correct
16 Correct 188 ms 391632 KB Output is correct
17 Correct 180 ms 390296 KB Output is correct
18 Correct 157 ms 389328 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 424788 KB Output is correct
2 Correct 280 ms 424872 KB Output is correct
3 Correct 986 ms 646724 KB Output is correct
4 Correct 355 ms 460544 KB Output is correct
5 Correct 1976 ms 915200 KB Output is correct
6 Correct 1579 ms 797896 KB Output is correct
7 Correct 150 ms 426840 KB Output is correct
8 Correct 147 ms 424788 KB Output is correct
9 Correct 130 ms 379996 KB Output is correct
10 Correct 136 ms 379072 KB Output is correct
11 Correct 146 ms 425564 KB Output is correct
12 Correct 132 ms 381212 KB Output is correct
13 Correct 267 ms 424796 KB Output is correct
14 Correct 215 ms 407592 KB Output is correct
15 Correct 207 ms 413280 KB Output is correct
16 Correct 193 ms 398164 KB Output is correct
17 Correct 485 ms 483672 KB Output is correct
18 Correct 466 ms 493588 KB Output is correct
19 Correct 321 ms 460368 KB Output is correct
20 Correct 328 ms 452532 KB Output is correct
21 Correct 611 ms 551008 KB Output is correct
22 Correct 1652 ms 920064 KB Output is correct
23 Correct 822 ms 563972 KB Output is correct
24 Correct 713 ms 604680 KB Output is correct
25 Correct 1753 ms 783524 KB Output is correct
26 Runtime error 591 ms 1048576 KB Execution killed with signal 9
27 Runtime error 605 ms 1048576 KB Execution killed with signal 9
28 Correct 1575 ms 797736 KB Output is correct
29 Correct 1480 ms 864036 KB Output is correct
30 Correct 1452 ms 1032072 KB Output is correct
31 Execution timed out 2081 ms 731968 KB Time limit exceeded
32 Runtime error 621 ms 1048576 KB Execution killed with signal 9