oj.uz

Submission #625174

# Submission time Handle Problem Language Result Execution time Memory
625174 2022-08-09T14:21:21 Z Stavab Tracks in the Snow (BOI13_tracks) C++14
17.6042 / 100
 2000 ms 945004 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++)
            if(field[i][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:85: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]
   85 |         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
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 13388 KB Output isn't correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 20 ms 8260 KB Output isn't correct
5 Incorrect 9 ms 4020 KB Output isn't correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Incorrect 1 ms 564 KB Output isn't correct
9 Incorrect 1 ms 724 KB Output isn't correct
10 Incorrect 8 ms 3412 KB Output isn't correct
11 Incorrect 5 ms 2388 KB Output isn't correct
12 Incorrect 16 ms 5048 KB Output isn't correct
13 Incorrect 9 ms 4052 KB Output isn't correct
14 Incorrect 9 ms 4052 KB Output isn't correct
15 Incorrect 40 ms 13096 KB Output isn't correct
16 Incorrect 45 ms 13440 KB Output isn't correct
17 Incorrect 33 ms 11740 KB Output isn't correct
18 Incorrect 19 ms 8348 KB Output isn't correct

Subtask #2
10.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2644 KB Output isn't correct
2 Incorrect 200 ms 73804 KB Output isn't correct
3 Incorrect 1452 ms 710864 KB Output isn't correct
4 Incorrect 394 ms 161008 KB Output isn't correct
5 Correct 929 ms 502372 KB Output is correct
6 Execution timed out 2110 ms 835536 KB Time limit exceeded
7 Incorrect 5 ms 2388 KB Output isn't correct
8 Incorrect 5 ms 2644 KB Output isn't correct
9 Incorrect 7 ms 2984 KB Output isn't correct
10 Correct 3 ms 1620 KB Output is correct
11 Incorrect 4 ms 2388 KB Output isn't correct
12 Correct 3 ms 1492 KB Output is correct
13 Incorrect 202 ms 73516 KB Output isn't correct
14 Incorrect 114 ms 42504 KB Output isn't correct
15 Incorrect 121 ms 45644 KB Output isn't correct
16 Incorrect 90 ms 31312 KB Output isn't correct
17 Incorrect 518 ms 189812 KB Output isn't correct
18 Incorrect 489 ms 181624 KB Output isn't correct
19 Incorrect 390 ms 161120 KB Output isn't correct
20 Incorrect 344 ms 153336 KB Output isn't correct
21 Incorrect 995 ms 413020 KB Output isn't correct
22 Correct 940 ms 502216 KB Output is correct
23 Incorrect 1022 ms 363500 KB Output isn't correct
24 Incorrect 868 ms 421344 KB Output isn't correct
25 Execution timed out 2036 ms 733516 KB Time limit exceeded
26 Correct 1173 ms 623408 KB Output is correct
27 Execution timed out 2127 ms 922236 KB Time limit exceeded
28 Execution timed out 2043 ms 835816 KB Time limit exceeded
29 Execution timed out 2089 ms 835056 KB Time limit exceeded
30 Execution timed out 2099 ms 879108 KB Time limit exceeded
31 Execution timed out 2084 ms 554968 KB Time limit exceeded
32 Execution timed out 2090 ms 945004 KB Time limit exceeded