oj.uz

Submission #1015784

# Submission time Handle Problem Language Result Execution time Memory
1015784 2024-07-06T19:06:08 Z KALARRY Tracks in the Snow (BOI13_tracks) C++14
82.5 / 100
 2000 ms 1048576 KB 
//chockolateman

#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int H,W,di[4] = {1,-1,0,0},dj[4] = {0,0,1,-1},dist[20000005];
char grid[4005][4005];
vector<pair<int,int>> adj[20000005];

int id(int i,int j)
{
    return (i-1)*W + j;
}

bool is_ok(int i,int j)
{
    if(i >= 1 && i <= H && j >= 1 && j <= W && grid[i][j] != '.')
        return true;
    return false;
}

void connect_neighs()
{
    for(int i = 1 ; i <= H ; i++)
        for(int j = 1 ; j <= W ; j++)
        {
            if(grid[i][j]=='.')
                continue;
            for(int k = 0 ; k <= 3 ; k++)
            {
                int new_i = i + di[k];
                int new_j = j + dj[k];
                if(is_ok(new_i,new_j))
                {
                    if(grid[i][j]==grid[new_i][new_j])
                        adj[id(i,j)].push_back({id(new_i,new_j),0});
                    else
                        adj[id(i,j)].push_back({id(new_i,new_j),1});
                }
            }
        }
}

void BFS(int start)
{
    for(int i = 1 ; i <= H ; i++)
        for(int j = 1 ; j <= W ; j++)
            if(grid[i][j]!='.')
                dist[id(i,j)] = INF;
    deque<int> q;
    dist[start] = 0;
    if(grid[1][1]!='.')
        dist[start] = 1;
    q.push_back(start);
    while(!q.empty())
    {
        int v = q.front();
        q.pop_front();
        for(auto e : adj[v])
        {
            int u = e.first;
            int w = e.second;
            if(dist[v] + w < dist[u])
            {
                dist[u] = dist[v] + w;
                if(w==0)
                    q.push_front(u);
                else
                    q.push_back(u);
            }
        }
    }
}

int main()
{
    scanf("%d%d",&H,&W);
    for(int i = 1 ; i <= H ; i++)
        for(int j = 1 ; j <= W ; j++)
            scanf(" %c",&grid[i][j]);
    connect_neighs();
    BFS(id(1,1));
    int ans = 0;
    for(int i = 1 ; i <= H ; i++)
        for(int j = 1 ; j <= W ; j++)
            ans = max(ans,dist[(id(i,j))]);
    printf("%d\n",ans);
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     scanf("%d%d",&H,&W);
      |     ~~~~~^~~~~~~~~~~~~~
tracks.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |             scanf(" %c",&grid[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 483848 KB Output is correct
2 Correct 169 ms 469980 KB Output is correct
3 Correct 180 ms 470216 KB Output is correct
4 Correct 204 ms 479912 KB Output is correct
5 Correct 175 ms 472252 KB Output is correct
6 Correct 184 ms 470100 KB Output is correct
7 Correct 172 ms 470256 KB Output is correct
8 Correct 173 ms 470352 KB Output is correct
9 Correct 185 ms 470548 KB Output is correct
10 Correct 183 ms 472452 KB Output is correct
11 Correct 191 ms 472916 KB Output is correct
12 Correct 191 ms 475220 KB Output is correct
13 Correct 224 ms 472252 KB Output is correct
14 Correct 188 ms 472096 KB Output is correct
15 Correct 209 ms 481108 KB Output is correct
16 Correct 220 ms 483920 KB Output is correct
17 Correct 197 ms 477332 KB Output is correct
18 Correct 209 ms 479824 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 485460 KB Output is correct
2 Correct 301 ms 509264 KB Output is correct
3 Correct 1028 ms 680532 KB Output is correct
4 Correct 399 ms 512592 KB Output is correct
5 Correct 689 ms 646272 KB Output is correct
6 Runtime error 1468 ms 1048576 KB Execution killed with signal 9
7 Correct 178 ms 486480 KB Output is correct
8 Correct 176 ms 485596 KB Output is correct
9 Correct 187 ms 471632 KB Output is correct
10 Correct 179 ms 470440 KB Output is correct
11 Correct 187 ms 485712 KB Output is correct
12 Correct 182 ms 470916 KB Output is correct
13 Correct 319 ms 509324 KB Output is correct
14 Correct 240 ms 493684 KB Output is correct
15 Correct 238 ms 487000 KB Output is correct
16 Correct 230 ms 489688 KB Output is correct
17 Correct 509 ms 563840 KB Output is correct
18 Correct 392 ms 528192 KB Output is correct
19 Correct 395 ms 512460 KB Output is correct
20 Correct 367 ms 525396 KB Output is correct
21 Correct 679 ms 601592 KB Output is correct
22 Correct 789 ms 646484 KB Output is correct
23 Correct 755 ms 645456 KB Output is correct
24 Correct 685 ms 596704 KB Output is correct
25 Correct 1086 ms 691024 KB Output is correct
26 Runtime error 1317 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1464 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1433 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1533 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1442 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2021 ms 1002064 KB Time limit exceeded
32 Runtime error 1375 ms 1048576 KB Execution killed with signal 9