oj.uz

Submission #931370

# Submission time Handle Problem Language Result Execution time Memory
931370 2024-02-21T16:39:08 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 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 163 ms 389208 KB Output is correct
2 Correct 124 ms 378192 KB Output is correct
3 Correct 122 ms 379264 KB Output is correct
4 Correct 132 ms 387716 KB Output is correct
5 Correct 123 ms 382548 KB Output is correct
6 Correct 119 ms 378200 KB Output is correct
7 Correct 114 ms 378708 KB Output is correct
8 Correct 116 ms 378712 KB Output is correct
9 Correct 114 ms 379260 KB Output is correct
10 Correct 120 ms 382020 KB Output is correct
11 Correct 118 ms 381524 KB Output is correct
12 Correct 129 ms 383312 KB Output is correct
13 Correct 119 ms 382568 KB Output is correct
14 Correct 118 ms 382596 KB Output is correct
15 Correct 142 ms 388688 KB Output is correct
16 Correct 153 ms 389204 KB Output is correct
17 Correct 135 ms 388184 KB Output is correct
18 Correct 122 ms 387668 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 424444 KB Output is correct
2 Correct 238 ms 416084 KB Output is correct
3 Correct 870 ms 593600 KB Output is correct
4 Correct 295 ms 440568 KB Output is correct
5 Correct 1472 ms 813020 KB Output is correct
6 Correct 1330 ms 679432 KB Output is correct
7 Correct 132 ms 426352 KB Output is correct
8 Correct 129 ms 424276 KB Output is correct
9 Correct 115 ms 379632 KB Output is correct
10 Correct 116 ms 378964 KB Output is correct
11 Correct 129 ms 425560 KB Output is correct
12 Correct 115 ms 380760 KB Output is correct
13 Correct 240 ms 416080 KB Output is correct
14 Correct 180 ms 402508 KB Output is correct
15 Correct 182 ms 406612 KB Output is correct
16 Correct 171 ms 393816 KB Output is correct
17 Correct 432 ms 461868 KB Output is correct
18 Correct 406 ms 467052 KB Output is correct
19 Correct 284 ms 440148 KB Output is correct
20 Correct 289 ms 439124 KB Output is correct
21 Correct 567 ms 518324 KB Output is correct
22 Correct 1473 ms 813040 KB Output is correct
23 Correct 741 ms 522832 KB Output is correct
24 Correct 610 ms 563296 KB Output is correct
25 Correct 1620 ms 676000 KB Output is correct
26 Runtime error 564 ms 1048576 KB Execution killed with signal 9
27 Runtime error 648 ms 1048576 KB Execution killed with signal 9
28 Correct 1383 ms 679556 KB Output is correct
29 Correct 1199 ms 730932 KB Output is correct
30 Correct 1176 ms 863112 KB Output is correct
31 Execution timed out 2051 ms 629212 KB Time limit exceeded
32 Runtime error 594 ms 1048576 KB Execution killed with signal 9