CSES - Datatähti 2025 loppu

Submission details
Task:	Suunnistus
Sender:	Vludo
Submission time:	2025-01-18 16:26:14 +0200
Language:	C++ (C++20)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	31
#2	ACCEPTED	12
#3	ACCEPTED	57

Test results
test	verdict	time	group
#1	ACCEPTED	0.00 s	3	details
#2	ACCEPTED	0.04 s	1, 2, 3	details
#3	ACCEPTED	0.04 s	1, 2, 3	details
#4	ACCEPTED	0.02 s	1, 2, 3	details
#5	ACCEPTED	0.01 s	1, 2, 3	details
#6	ACCEPTED	0.00 s	1, 2, 3	details
#7	ACCEPTED	0.22 s	2, 3	details
#8	ACCEPTED	0.22 s	2, 3	details
#9	ACCEPTED	0.02 s	2, 3	details
#10	ACCEPTED	0.44 s	3	details
#11	ACCEPTED	0.46 s	3	details
#12	ACCEPTED	0.02 s	3	details
#13	ACCEPTED	0.24 s	3	details
#14	ACCEPTED	0.05 s	2, 3	details
#15	ACCEPTED	0.01 s	3	details
#16	ACCEPTED	0.00 s	3	details
#17	ACCEPTED	0.02 s	2, 3	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:83:9: warning: unused variable 'summa' [-Wunused-variable]
   83 |     int summa = 0;
      |         ^~~~~

Code

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define F first 
#define S second
#define N 505
 
int n, m, k;
char arr[N][N];
int vis[N][N];
vector<pair<pii, int>> v;
int kohteet[11];
 
void bfs(char kohde, int visiit) {
    priority_queue<pair<int, pii>> q;
    for (auto i : v) {
        q.push({-i.S, i.F});
    }
    v.clear();
    while (!q.empty()) {
        // if (v.size()==kohteet[kohde-'0']) break; 
        auto[x, paikka] = q.top();
        q.pop();
 
        // cout << kohde << ' ' << paikka.F << ' ' << paikka.S << endl;
 
        if (paikka.F>0 && vis[paikka.F-1][paikka.S]!=visiit) {
            vis[paikka.F-1][paikka.S] = visiit;
            char ch = arr[paikka.F-1][paikka.S];
            if (ch==kohde) {
                v.push_back({{paikka.F-1,paikka.S},-x+1});
                // if (kohde == '0'+k+1) return;
            }
            if (ch!='#') q.push({x-1,{paikka.F-1,paikka.S}});
        }
        if (paikka.F<n-1 && vis[paikka.F+1][paikka.S]!=visiit) {
            vis[paikka.F+1][paikka.S] = visiit;
            char ch = arr[paikka.F+1][paikka.S];
            if (ch==kohde) {
                v.push_back({{paikka.F+1,paikka.S},-x+1});
                // if (kohde == '0'+k+1) return;
            }
            if (ch!='#') q.push({x-1, {paikka.F+1,paikka.S}});
        }
        if (paikka.S>0 && vis[paikka.F][paikka.S-1]!=visiit) {
            vis[paikka.F][paikka.S-1] = visiit;
            char ch = arr[paikka.F][paikka.S-1];
            if (ch==kohde) {
                v.push_back({{paikka.F,paikka.S-1},-x+1});
                // if (kohde == '0'+k+1) return;
            }
            if (ch!='#') q.push({x-1, {paikka.F,paikka.S-1}});
        }
        if (paikka.S<m-1 && vis[paikka.F][paikka.S+1]!=visiit) {
            vis[paikka.F][paikka.S+1] = visiit;
            char ch = arr[paikka.F][paikka.S+1];
            if (ch==kohde) {
                v.push_back({{paikka.F,paikka.S+1},-x+1});
                // if (kohde == '0'+k+1) return;
            }
            if (ch!='#') q.push({x-1, {paikka.F,paikka.S+1}});
        }
    }
}
 
int main() {
    cin >> n >> m >> k;
    pii start;
    for (int i=0;i<n;++i) {
        for (int j=0;j<m;++j) {
            cin >> arr[i][j];
            if (arr[i][j]>='0' && arr[i][j]<='9') 
                kohteet[arr[i][j]-'0']++;
            else if (arr[i][j]=='E') arr[i][j] = '0'+k+1;
            else if (arr[i][j]=='S') start = {i,j};
        }
    }
    for (int i = 1; i<=k; ++i) {
        if (!kohteet[i])
            return 0*printf("-1\n");
    }
    kohteet[k+1] = 1;
    int summa = 0;
    v.push_back({start, 0});

    for (int kohde=1;kohde<=k+1;++kohde) if (kohteet[kohde]) {
        if (v.empty()) return 0*printf("-1\n");
        bfs('0'+kohde, kohde);
        // for (auto i : v) cout << "{ " << i.F.F << " " << i.F.S << ": " << i.S << " }, "; 
        // cout << endl;
    } else return 0*printf("-1\n");
 
    if (v.empty()) return 0*printf("-1\n");
    for (auto i : v) cout << i.S << ' ';
    cout << 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: ACCEPTED

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

correct output
`-1` view save

user output
`-1` view save

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: ACCEPTED

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

correct output
`3447` view save

user output
`3447` view save

Test 8

Group: 2, 3

Verdict: ACCEPTED

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

correct output
`4952` view save

user output
`4952` view save

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: ACCEPTED

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

correct output
`205` view save

user output
`205` view save

Test 11

Group: 3

Verdict: ACCEPTED

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

correct output
`157` view save

user output
`157` view save

Test 12

Group: 3

Verdict: ACCEPTED

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

correct output
`-1` view save

user output
`-1` view save

Test 13

Group: 3

Verdict: ACCEPTED

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

correct output
`1313` view save

user output
`1313` view save

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

Compiler report

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 (Vludo)