Submission #1026602

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1026602	2024-07-18T08:32:39 Z	vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	82.5 / 100	2000 ms	104844 KB

tracks

#include <bits/stdc++.h>

using namespace std;

int dr[]={+1, 0, -1, 0};
int dc[]={0, +1, 0, -1};

int main()
{
    iostream::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    char tracks[n][m];
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            cin >> tracks[i][j];
    priority_queue<pair<int, pair<int,int> > > pq;
    pq.push({-1, {0,0}});
    int vis[n][m], rez=1;
    memset(vis, -1, sizeof(vis));
    while (!pq.empty()) {
        int r=pq.top().second.first, c=pq.top().second.second, dist=-pq.top().first;
        pq.pop();
        if (vis[r][c]!=-1) continue;
        vis[r][c]=dist;
        rez=max(rez, dist);
        for (int i=0;i<4;i++) {
            int nr=r+dr[i], nc=c+dc[i];
            if (nr>=0&&nc>=0&&nr<n&&nc<m&&tracks[nr][nc]!='.') {
                if (tracks[nr][nc]!=tracks[r][c]) pq.push({-(dist+1), {nr, nc}});
                else pq.push({-dist, {nr, nc}});
            }
        }
    }
    cout << rez;

    return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	2072 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	67 ms	2088 KB	Output is correct
5	Correct	7 ms	860 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	10 ms	812 KB	Output is correct
11	Correct	16 ms	900 KB	Output is correct
12	Correct	42 ms	1112 KB	Output is correct
13	Correct	7 ms	860 KB	Output is correct
14	Correct	7 ms	860 KB	Output is correct
15	Correct	84 ms	1880 KB	Output is correct
16	Correct	121 ms	2076 KB	Output is correct
17	Correct	40 ms	1628 KB	Output is correct
18	Correct	67 ms	1868 KB	Output is correct

Subtask #2

52.5 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	604 KB	Output is correct
2	Correct	259 ms	8028 KB	Output is correct
3	Correct	855 ms	78864 KB	Output is correct
4	Correct	191 ms	18780 KB	Output is correct
5	Correct	261 ms	44628 KB	Output is correct
6	Execution timed out	2023 ms	103624 KB	Time limit exceeded
7	Correct	2 ms	600 KB	Output is correct
8	Correct	2 ms	600 KB	Output is correct
9	Correct	11 ms	860 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	251 ms	8256 KB	Output is correct
14	Correct	146 ms	4956 KB	Output is correct
15	Correct	21 ms	5208 KB	Output is correct
16	Correct	149 ms	3744 KB	Output is correct
17	Correct	618 ms	20560 KB	Output is correct
18	Correct	86 ms	20052 KB	Output is correct
19	Correct	211 ms	18772 KB	Output is correct
20	Correct	206 ms	17236 KB	Output is correct
21	Correct	544 ms	46160 KB	Output is correct
22	Correct	259 ms	44560 KB	Output is correct
23	Correct	1447 ms	38484 KB	Output is correct
24	Correct	229 ms	44904 KB	Output is correct
25	Correct	476 ms	78896 KB	Output is correct
26	Execution timed out	2083 ms	60556 KB	Time limit exceeded
27	Execution timed out	2060 ms	80332 KB	Time limit exceeded
28	Execution timed out	2037 ms	104844 KB	Time limit exceeded
29	Execution timed out	2068 ms	104560 KB	Time limit exceeded
30	Execution timed out	2041 ms	102480 KB	Time limit exceeded
31	Execution timed out	2077 ms	54100 KB	Time limit exceeded
32	Execution timed out	2075 ms	80236 KB	Time limit exceeded