CSES - Datatähti 2025 loppu

CSES - Datatähti 2025 loppu - Results

Submission details
Task:	Suunnistus
Sender:	Verlet
Submission time:	2025-01-18 20:51:56 +0200
Language:	C++ (C++17)
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	RUNTIME ERROR	0
#2	RUNTIME ERROR	0
#3	RUNTIME ERROR	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	3	details
#2	ACCEPTED	0.16 s	1, 2, 3	details
#3	ACCEPTED	0.15 s	1, 2, 3	details
#4	RUNTIME ERROR	0.02 s	1, 2, 3	details
#5	ACCEPTED	0.00 s	1, 2, 3	details
#6	ACCEPTED	0.00 s	1, 2, 3	details
#7	TIME LIMIT EXCEEDED	--	2, 3	details
#8	TIME LIMIT EXCEEDED	--	2, 3	details
#9	ACCEPTED	0.02 s	2, 3	details
#10	TIME LIMIT EXCEEDED	--	3	details
#11	TIME LIMIT EXCEEDED	--	3	details
#12	WRONG ANSWER	0.02 s	3	details
#13	TIME LIMIT EXCEEDED	--	3	details
#14	ACCEPTED	0.17 s	2, 3	details
#15	ACCEPTED	0.01 s	3	details
#16	ACCEPTED	0.01 s	3	details
#17	ACCEPTED	0.15 s	2, 3	details

Code

#include <bits/stdc++.h>

#define N 502

#define F first
#define S second

#define pb push_back

using namespace std;

typedef pair<int, int> ip;

typedef pair<int, ip> Node;

char m[N][N];
char v[N][N];

void reset()
{
  for (int y = 0; y < N; y++)
  for (int x = 0; x < N; x++)
  {
    v[x][y] = false;
  }
}

void bfs(vector<Node> & start, vector<Node> & end, char target)
{
  priority_queue<Node, vector<Node>, greater<Node>> q;

  for (Node n : start) q.push(n);

  while (q.size())
  {
    Node n = q.top(); q.pop();

    int d = n.F;
    int x = n.S.F;
    int y = n.S.S;

    if (v[x][y] || m[x][y] == '#') continue;

    v[x][y] = true;

    if (m[x][y] == target) end.pb(n);

    q.push({d+1, {x+1, y}});
    q.push({d+1, {x-1, y}});
    q.push({d+1, {x, y+1}});
    q.push({d+1, {x, y-1}});
  }
}

int main()
{
  int w, h, k; cin >> h >> w >> k;

  for (int y = 0; y < N; y++)
  for (int x = 0; x < N; x++)
  {
    m[x][y] = '#';
  }

  ip s, e;

  // cout << "Width: " << w << endl;
  // cout << "Height: " << h << endl;

  for (int y = 1; y <= h; y++)
  for (int x = 1; x <= w; x++)
  {
    char c; cin >> c;

    if (c != '#') m[x][y] = c;

    if (c == 'S') s = {x, y};
    if (c == 'E') e = {x, y};
  }

  // cout << "Start: " << s.F << " " << s.S << endl;
  // cout << "End: " << e.F << " " << e.S << endl;

  // for (int y = 0; y <= h + 1; y++)
  // {
  //   for (int x = 0; x <= w + 1; x++)
  //   {
  //     cout << m[x][y] << " ";
  //   }
  //   cout << endl;
  // }

  vector<Node> start, end;

  start.pb({0, s});

  for (char c = '1'; c < '1' + k; c++)
  {
    bfs(start, end, c);
    reset();

    start.clear();
    for (Node n : end) start.pb(n);
    end.clear();

    if (start.size() == 0)
    {
      cout << -1 << endl;
      exit(0);
    }
  }

  bfs(start, end, 'E');

  cout << end[0].F << endl;
}

Test details

Test 1

Group: 3

Verdict: ACCEPTED

input
`10 10 9 S293#35616 #662963731 54975451#7 5162589168 ...` view save

correct output
`25` view save

user output
`25` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`500 500 0 .................................` view save

correct output
`301` view save

user output
`301` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`500 500 0 .#.........#.#..##..#............` view save

correct output
`253` view save

user output
`253` view save

Test 4

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`500 500 0 ...#......##.##.#.#..##..#..##...` view save

correct output
`-1` view save

user output
(empty)

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`500 1 0 . . . . ...` view save

correct output
`77` view save

user output
`77` view save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1 500 0 .................................` view save

correct output
`166` view save

user output
`166` view save

Test 7

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`500 500 9 .................................` view save

correct output
`3447` view save

user output
(empty)

Test 8

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`500 500 9 .#........#..................#...` view save

correct output
`4952` view save

user output
(empty)

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
`500 500 9 ##.########.##########.#..#......` view save

correct output
`-1` view save

user output
`-1` view save

Test 10

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`500 500 9 623475428948841896621266296765...` view save

correct output
`205` view save

user output
(empty)

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`500 500 9 7##814125813#3463#272134469457...` view save

correct output
`157` view save

user output
(empty)

Test 12

Group: 3

Verdict: WRONG ANSWER

input
`500 500 9 ##67##36##5#3###67###8972#61##...` view save

correct output
`-1` view save

user output
`23` view save

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`500 500 9 ....................#...#........` view save

correct output
`1313` view save

user output
(empty)

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
`499 499 9 S#...#...#...#...#...#...#...#...` view save

correct output
`1124942` view save

user output
`1124942` view save

Test 15

Group: 3

Verdict: ACCEPTED

input
`500 1 9 1 6 1 3 ...` view save

correct output
`332` view save

user output
`332` view save

Test 16

Group: 3

Verdict: ACCEPTED

input
`1 500 9 996327784392827829434482995353...` view save

correct output
`135` view save

user output
`135` view save

Test 17

Group: 2, 3

Verdict: ACCEPTED

input
`500 500 9 .................................` view save

correct output
`-1` view save

user output
`-1` view save

Datatähti 2025 loppu

Suunnistus

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Tasks

Submissions (Verlet)