oj.uz

Submission #625160

# Submission time Handle Problem Language Result Execution time Memory
625160 2022-08-09T14:01:39 Z Stavab Tracks in the Snow (BOI13_tracks) C++14
80.3125 / 100
 2000 ms 1048576 KB 
#include <iostream>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

vector<vector<char>> field;
int h, w, answer = 1;
vector<int> father, chainSize, turn, put;
vector<vector<pair<int, int>>> points;

int find(int n)
{
    if(father[n] != n)
        father[n] = find(father[n]);
        
    return father[n];
}

void join(int a, int b)
{
    a = find(a);
    b = find(b);
    
    if(a == b)
        return;
    
    if(chainSize[a] < chainSize[b])
        swap(a, b);
    
    father[b] = a;
    chainSize[a] += chainSize[b];
}

int main()
{
    scanf("%d %d", &h, &w);
    
    field.assign(h, vector<char>(w));
    father.assign(h*w, 0);
    chainSize.assign(h*w, 1);
    turn.assign(h*w, 0);
    points.assign(h*w, vector<pair<int, int>>());
    put.assign(h*w, 0);
    
    for(int i = 0; i < h; i++)
    {
        for(int j = 0; j < w; j++)
        {
            scanf(" %c", &field[i][j]);
            father[i*w + j] = i*w + j;
            
            if(field[i][j] == '.')
                continue;
            
            if(i != 0)
            {
                if(field[i - 1][j] == field[i][j])
                    join(i*w + j, (i - 1)*w + j);
            }
            if(j != 0)
            {
                if(field[i][j - 1] == field[i][j])
                    join(i*w + j, i*w + j - 1);
            }
        }
    }
    
    for(int i = 0; i < h; i++)
    {
        for(int j = 0; j < w; j++)
            points[find(i*w + j)].push_back(make_pair(i, j));
    }
    turn[find(0)] = 1;
    
    queue<int> q;
    q.push(find(0));
    put[find(0)] = 1;
    
    while(!q.empty())
    {
        int cur = q.front();
        answer = max(answer, turn[cur]);
        
        for(int i = 0; i < points[cur].size(); i++)
        {
            int a = points[cur][i].first;
            int b = points[cur][i].second;
            
            if(a != 0)
            {
                if(field[a - 1][b] != '.' && find((a - 1)*w + b) != cur)
                {
                    if(!put[find((a - 1)*w + b)])
                    {
                        turn[find((a - 1)*w + b)] = turn[cur] + 1;
                        q.push(find((a - 1)*w + b));
                        put[find((a - 1)*w + b)] = 1;
                    }
                }
            }
            if(b != 0)
            {
                if(field[a][b - 1] != '.' && find(a*w + b - 1) != cur)
                {
                    if(!put[find(a*w + b - 1)])
                    {
                        turn[find(a*w + b - 1)] = turn[cur] + 1;
                        q.push(find(a*w + b - 1));
                        put[find(a*w + b - 1)] = 1;
                    }
                }
            }
            if(a != h - 1)
            {
                if(field[a + 1][b] != '.' && find((a + 1)*w + b) != cur)
                {
                    if(!put[find((a + 1)*w + b)])
                    {
                        turn[find((a + 1)*w + b)] = turn[cur] + 1;
                        q.push(find((a + 1)*w + b));
                        put[find((a + 1)*w + b)] = 1;
                    }
                }
            }
            if(b != w - 1)
            {
                if(field[a][b + 1] != '.' && find(a*w + b + 1) != cur)
                {
                    if(!put[find(a*w + b + 1)])
                    {
                        turn[find(a*w + b + 1)] = turn[cur] + 1;
                        q.push(find(a*w + b + 1));
                        put[find(a*w + b + 1)] = 1;
                    }
                }
            }
        }
               
        q.pop();
    }
    
    printf("%d\n", answer);
    
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:86:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int i = 0; i < points[cur].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~~~~~
tracks.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d %d", &h, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:51:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |             scanf(" %c", &field[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 13524 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 25 ms 8032 KB Output is correct
5 Correct 14 ms 6100 KB Output is correct
6 Correct 4 ms 212 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 11 ms 4536 KB Output is correct
11 Correct 6 ms 2388 KB Output is correct
12 Correct 17 ms 5168 KB Output is correct
13 Correct 15 ms 6068 KB Output is correct
14 Correct 14 ms 6068 KB Output is correct
15 Correct 51 ms 15308 KB Output is correct
16 Correct 62 ms 13552 KB Output is correct
17 Correct 55 ms 15880 KB Output is correct
18 Correct 24 ms 8036 KB Output is correct

Subtask #2
50.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3764 KB Output is correct
2 Correct 276 ms 102880 KB Output is correct
3 Runtime error 1728 ms 1048576 KB Execution killed with signal 9
4 Correct 823 ms 263928 KB Output is correct
5 Correct 1255 ms 649044 KB Output is correct
6 Execution timed out 2097 ms 816516 KB Time limit exceeded
7 Correct 10 ms 3412 KB Output is correct
8 Correct 12 ms 3868 KB Output is correct
9 Correct 10 ms 4072 KB Output is correct
10 Correct 6 ms 2388 KB Output is correct
11 Correct 10 ms 3668 KB Output is correct
12 Correct 4 ms 1844 KB Output is correct
13 Correct 318 ms 103196 KB Output is correct
14 Correct 177 ms 59504 KB Output is correct
15 Correct 223 ms 68968 KB Output is correct
16 Correct 141 ms 40904 KB Output is correct
17 Correct 890 ms 268156 KB Output is correct
18 Correct 837 ms 276100 KB Output is correct
19 Correct 642 ms 264036 KB Output is correct
20 Correct 508 ms 236252 KB Output is correct
21 Correct 1322 ms 638244 KB Output is correct
22 Correct 1204 ms 649004 KB Output is correct
23 Correct 1368 ms 508388 KB Output is correct
24 Correct 1267 ms 617684 KB Output is correct
25 Runtime error 1764 ms 1048576 KB Execution killed with signal 9
26 Correct 1756 ms 629248 KB Output is correct
27 Execution timed out 2069 ms 829948 KB Time limit exceeded
28 Execution timed out 2100 ms 816648 KB Time limit exceeded
29 Execution timed out 2072 ms 795628 KB Time limit exceeded
30 Execution timed out 2108 ms 780524 KB Time limit exceeded
31 Execution timed out 2128 ms 554052 KB Time limit exceeded
32 Execution timed out 2113 ms 854668 KB Time limit exceeded