Submission #625138

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
625138	2022-08-09T13:07:09 Z	Stavab	Tracks in the Snow (BOI13_tracks)	C++14	47.5 / 100	2000 ms	156960 KB

tracks

#include <iostream>
#include <vector>

using namespace std;

vector<vector<char>> field;
int h, w, prints = 0;
vector<int> father, chainSize;

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 animals(char curPrint)
{
    if(chainSize[find(0)] == prints)
        return 1;
        

    int cur = find(0);
    for(int i = 0; i < h; i++)
    {
        for(int j = 0; j < w; j++)
        {
            if(field[i][j] != curPrint)
                continue;
                
            if(i != 0)
            {
                if(find((i - 1)*w + j) == cur)
                    join(i*w + j, 0);
            }
            if(j != 0)
            {
                if(find(i*w + j - 1) == cur)
                    join(i*w + j, 0);
            }
            if(i != h - 1)
            {
                if(find((i + 1)*w + j) == cur)
                    join(i*w + j, 0);
            }
            if(j != w - 1)
            {
                if(find(i*w + j + 1) == cur)
                    join(i*w + j, 0);
            }
        }
    }
    
    if(curPrint == 'R')
        return animals('F') + 1;
    return animals('R') + 1;
}

int main()
{
    scanf("%d %d", &h, &w);
    
    field.assign(h, vector<char>(w));
    father.assign(h*w, 0);
    chainSize.assign(h*w, 1);
    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;
            
            prints++;        
            
            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);
            }
        }
    }
    
    if(field[0][0] == 'F')
        printf("%d\n", animals('R'));
    else
        printf("%d\n", animals('F'));
    
    return 0;
}

Compilation message

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

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	271 ms	2668 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	2 ms	212 KB	Output is correct
4	Correct	29 ms	1828 KB	Output is correct
5	Correct	59 ms	1136 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	2 ms	292 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	3 ms	340 KB	Output is correct
10	Correct	93 ms	852 KB	Output is correct
11	Correct	7 ms	596 KB	Output is correct
12	Correct	84 ms	1152 KB	Output is correct
13	Correct	58 ms	1128 KB	Output is correct
14	Correct	57 ms	1108 KB	Output is correct
15	Correct	571 ms	2772 KB	Output is correct
16	Correct	267 ms	2644 KB	Output is correct
17	Correct	394 ms	2764 KB	Output is correct
18	Correct	29 ms	1748 KB	Output is correct

Subtask #2

17.5 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1567 ms	1860 KB	Output is correct
2	Execution timed out	2052 ms	15760 KB	Time limit exceeded
3	Execution timed out	2055 ms	156952 KB	Time limit exceeded
4	Execution timed out	2085 ms	37076 KB	Time limit exceeded
5	Execution timed out	2068 ms	88572 KB	Time limit exceeded
6	Execution timed out	2068 ms	156956 KB	Time limit exceeded
7	Correct	1109 ms	1656 KB	Output is correct
8	Correct	1480 ms	1804 KB	Output is correct
9	Correct	175 ms	892 KB	Output is correct
10	Correct	352 ms	992 KB	Output is correct
11	Correct	354 ms	1208 KB	Output is correct
12	Correct	1226 ms	2548 KB	Output is correct
13	Execution timed out	2061 ms	15764 KB	Time limit exceeded
14	Execution timed out	2071 ms	9292 KB	Time limit exceeded
15	Execution timed out	2066 ms	10264 KB	Time limit exceeded
16	Execution timed out	2074 ms	6832 KB	Time limit exceeded
17	Execution timed out	2076 ms	40152 KB	Time limit exceeded
18	Execution timed out	2076 ms	39560 KB	Time limit exceeded
19	Execution timed out	2053 ms	37168 KB	Time limit exceeded
20	Execution timed out	2093 ms	34032 KB	Time limit exceeded
21	Execution timed out	2068 ms	91540 KB	Time limit exceeded
22	Execution timed out	2044 ms	88452 KB	Time limit exceeded
23	Execution timed out	2035 ms	76148 KB	Time limit exceeded
24	Execution timed out	2069 ms	89352 KB	Time limit exceeded
25	Execution timed out	2028 ms	156960 KB	Time limit exceeded
26	Correct	991 ms	120208 KB	Output is correct
27	Execution timed out	2074 ms	156956 KB	Time limit exceeded
28	Execution timed out	2099 ms	156952 KB	Time limit exceeded
29	Execution timed out	2098 ms	156956 KB	Time limit exceeded
30	Execution timed out	2086 ms	153676 KB	Time limit exceeded
31	Execution timed out	2072 ms	100648 KB	Time limit exceeded
32	Execution timed out	2086 ms	156960 KB	Time limit exceeded